[PATCH 1/1]: Fix packet tardiness bug in CCID 3

[PATCH 1/1]: Fix packet tardiness bug in CCID 3

[Gerrit Renker]

[CCID 3]: Fix packet tardiness BUG

 This fixes a bug introduced by myself. 

 A huge lot of thanks to Ian McDonald who identified this bug. 

Problem:
--------
 Due to packet scheduling in CCID 3, it can happen that the
 actual send time of a packet is later than t_now: in this case
 t_nom < t_now. 
 This case brings the entire packet scheduling out of sync, since
 the next packet is scheduled at t_nom + t_ipi, and t_nom is in
 the past.

Fix:
----
 Update t_nom to t_now whenever a packet is late due to scheduling
 (and then t_nom < t_now). This update takes place in ccid3_hc_tx_
 send_packet. In between calls to this function, it is irrelevant
 if t_nom < t_now (since it will be caught eventually). 

Signed-off-by: Gerrit Renker <gerrit@erg.abdn.ac.uk> 
---
 net/dccp/ccids/ccid3.c |    6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

--- a/net/dccp/ccids/ccid3.c
+++ b/net/dccp/ccids/ccid3.c
@@ -349,7 +349,9 @@ static int ccid3_hc_tx_send_packet(struc
 	case TFRC_SSTATE_NO_FBACK:
 	case TFRC_SSTATE_FBACK:
 		delay = timeval_delta(&hctx->ccid3hctx_t_nom, &now);
-		ccid3_pr_debug("delay=%ld\n", (long)delay);
+		/* handle packet tardiness: synchronise t_nom with send time */
+		if (delay < 0)
+			hctx->ccid3hctx_t_nom = now;
 		/*
 		 *	Scheduling of packet transmissions [RFC 3448, 4.6]
 		 *
@@ -358,7 +360,7 @@ static int ccid3_hc_tx_send_packet(struc
 		 * else
 		 *       // send the packet in (t_nom - t_now) milliseconds.
 		 */
-		if (delay - (suseconds_t)hctx->ccid3hctx_delta >= 0)
+		else if (delay - (suseconds_t)hctx->ccid3hctx_delta >= 0)
 			return delay / 1000L;
 
 		ccid3_hc_tx_update_win_count(hctx, &now);

Re: [PATCH 1/1]: Fix packet tardiness bug in CCID 3

[Ian McDonald]

On 12/22/06, Gerrit Renker <gerrit@erg.abdn.ac.uk> wrote:
> [CCID 3]: Fix packet tardiness BUG
>
> Problem:
> --------
>  Due to packet scheduling in CCID 3, it can happen that the
>  actual send time of a packet is later than t_now: in this case
>  t_nom < t_now.
>  This case brings the entire packet scheduling out of sync, since
>  the next packet is scheduled at t_nom + t_ipi, and t_nom is in
>  the past.
>
> Fix:
> ----
>  Update t_nom to t_now whenever a packet is late due to scheduling
>  (and then t_nom < t_now). This update takes place in ccid3_hc_tx_
>  send_packet. In between calls to this function, it is irrelevant
>  if t_nom < t_now (since it will be caught eventually).
>
Agree with the problem statement and your fix helps but I think this
fix isn't quite right and mine uses a bit too much CPU resource.

The problem with yours is that it resets t_nom whenever it is late
rather than just due to t_ipi changing. The problem like this is that
if the packet is late for other reasons then we shouldn't slow down
following packets as it hurts performance. Many cases the result will
be negative but low value.

I'll go back and rework my patch a little.

Ian
-- 
Web: http://wand.net.nz/~iam4
Blog: http://imcdnzl.blogspot.com
WAND Network Research Group

Re: [PATCH 1/1]: Fix packet tardiness bug in CCID 3

[Gerrit Renker]

Ian,

I really do appreciate your effort and your input has been helpful, but
do you not agree that such a bug needs to be tackled at the root?
Please see below.

|  > [CCID 3]: Fix packet tardiness BUG
|  >
|  > Problem:
|  > --------
|  >  Due to packet scheduling in CCID 3, it can happen that the
|  >  actual send time of a packet is later than t_now: in this case
|  >  t_nom < t_now.
|  >  This case brings the entire packet scheduling out of sync, since
|  >  the next packet is scheduled at t_nom + t_ipi, and t_nom is in
|  >  the past.
|  >
|  > Fix:
|  > ----
|  >  Update t_nom to t_now whenever a packet is late due to scheduling
|  >  (and then t_nom < t_now). This update takes place in ccid3_hc_tx_
|  >  send_packet. In between calls to this function, it is irrelevant
|  >  if t_nom < t_now (since it will be caught eventually).
|  >
|  Agree with the problem statement and your fix helps but I think this
|  fix isn't quite right and mine uses a bit too much CPU resource.

|  
|  The problem with yours is that it resets t_nom whenever it is late
|  rather than just due to t_ipi changing. 
Sorry, did you read the earlier emails that I sent? The point is that
t_ipi will never cause t_nom to become negative. Let things be what they
may - one thing is clear: the problem of being too late in scheduling must
be accounted for. This is what the patch does.

There is a second issue which is more subtle: there are several functions
which access t_nom asynchronously: packet_sent, packet_recv, no_feedback timer.
Due to concurrency this means that we have a race condition if we allow
several functions to access t_nom without enforcing mutual exclusion via
locks: the problem is that one function can read an old t_nom, while t_ipi
has just been subtracted .... and so on. I have prepared another patch to
take care of this.


|  The problem like this is that if the packet is late for other reasons 
|  then we shouldn't slow down following packets as it hurts performance. 
Ian, which `other reasons' do you mean?: it is logically impossible to create
a t_nom < t_now other than being too late in scheduling.

Gerrit