[PATCH 6/25] Reduce allowed sending rate by a factor that accounts for packet header size

[PATCH 6/25] Reduce allowed sending rate by a factor that accounts for packet header size

[Leandro]

[CCID-4] Reduce allowed sending rate by a factor that accounts for packet header size

Signed-off-by: Leandro Melo de Sales <leandro@embedded.ufcg.edu.br>
Signed-off-by: Tommi Saviranta <wnd@iki.fi>

Index: leandro.new/net/dccp/ccids/ccid4.c
=================================--- leandro.new.orig/net/dccp/ccids/ccid4.c
+++ leandro.new/net/dccp/ccids/ccid4.c
@@ -135,6 +135,17 @@ static u32 ccid4_hc_tx_idle_rtt(struct c
 }
 
 /**
+ * ccid4_hc_tx_x_header_penalty  -  Update allower sending rate X
+ * @hctx: half-connection to adjust
+ * This function adjusts sending rate according to [TFRC-SP, Section 5]
+ */
+static inline void ccid4_hc_tx_x_header_penalty(struct ccid4_hc_tx_sock *hctx)
+{
+        hctx->ccid4hctx_x *= hctx->ccid4hctx_s;
+        do_div(hctx->ccid4hctx_x, (hctx->ccid4hctx_s + CCID4HCTX_H));
+}
+
+/**
  * ccid4_hc_tx_update_x  -  Update allowed sending rate X
  * @stamp: most recent time if available - can be left NULL.
  * This function tracks draft rfc3448bis, check there for latest details.
@@ -170,6 +181,7 @@ static void ccid4_hc_tx_update_x(struct 
 		hctx->ccid4hctx_x = max(hctx->ccid4hctx_x,
 					(((__u64)hctx->ccid4hctx_s) << 6) /
 								TFRC_T_MBI);
+                ccid4_hc_tx_x_header_penalty(hctx);
 
 	} else if (ktime_us_delta(now, hctx->ccid4hctx_t_ld)
 				- (s64)hctx->ccid4hctx_rtt >= 0) {
@@ -178,6 +190,8 @@ static void ccid4_hc_tx_update_x(struct 
 			max(min(2 * hctx->ccid4hctx_x, min_rate),
 			    scaled_div(((__u64)hctx->ccid4hctx_s) << 6,
 				       hctx->ccid4hctx_rtt));
+
+                ccid4_hc_tx_x_header_penalty(hctx);
 		hctx->ccid4hctx_t_ld = now;
 	}
 
Index: leandro.new/net/dccp/ccids/ccid4.h
=================================--- leandro.new.orig/net/dccp/ccids/ccid4.h
+++ leandro.new/net/dccp/ccids/ccid4.h
@@ -71,6 +71,11 @@
 /* Mininum sending rate as per CCID-4 draft */
 #define MIN_SEND_RATE              10000
 
+/* The header size on data packets is estimated as 36 bytes as per CCID-4
+ * draft, [Section 5].
+ */
+#define CCID4HCTX_H    36
+
 enum ccid4_options {
 	TFRC_OPT_LOSS_EVENT_RATE = 192,
 	TFRC_OPT_LOSS_INTERVALS	 = 193,

Re: [PATCH 6/25] Reduce allowed sending rate by a factor that accounts for packet header size

[Ian McDonald]

On 11/1/07, Leandro <leandroal@gmail.com> wrote:
> [CCID-4] Reduce allowed sending rate by a factor that accounts for packet header size
>
> Signed-off-by: Leandro Melo de Sales <leandro@embedded.ufcg.edu.br>
> Signed-off-by: Tommi Saviranta <wnd@iki.fi>

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

Re: [PATCH 6/25] Reduce allowed sending rate by a factor that accounts for packet header size

[Gerrit Renker]

| @@ -170,6 +181,7 @@ static void ccid4_hc_tx_update_x(struct 
|  		hctx->ccid4hctx_x = max(hctx->ccid4hctx_x,
|  					(((__u64)hctx->ccid4hctx_s) << 6) /
|  								TFRC_T_MBI);
| +                ccid4_hc_tx_x_header_penalty(hctx);
|  
|  	} else if (ktime_us_delta(now, hctx->ccid4hctx_t_ld)
|  				- (s64)hctx->ccid4hctx_rtt >= 0) {
| @@ -178,6 +190,8 @@ static void ccid4_hc_tx_update_x(struct 
|  			max(min(2 * hctx->ccid4hctx_x, min_rate),
|  			    scaled_div(((__u64)hctx->ccid4hctx_s) << 6,
|  				       hctx->ccid4hctx_rtt));
| +
| +                ccid4_hc_tx_x_header_penalty(hctx);
|  		hctx->ccid4hctx_t_ld = now;
|  	}
Since ccid4_hc_tx_x_header_penalty() is called in both the if/else
branches, it looks to me that you can put it before the if/else. 
If you then wanted to abstract this function, it looks as if a wrapper
could be used:

	ccid4_hc_tx_update_x(hctx) 
	{
                ccid4_hc_tx_x_header_penalty(hctx);
		tfrc_hc_tx_update_x(...);
	}

Makes sense?

Re: [PATCH 6/25] Reduce allowed sending rate by a factor that

[Tommi Saviranta]

On Thu, Nov 08, 2007 at 10:15:23 +0000, Gerrit Renker wrote:
> Since ccid4_hc_tx_x_header_penalty() is called in both the if/else
> branches, it looks to me that you can put it before the if/else. 
> If you then wanted to abstract this function, it looks as if a wrapper
> could be used:
> 
> 	ccid4_hc_tx_update_x(hctx) 
> 	{
>               ccid4_hc_tx_x_header_penalty(hctx);
> 		tfrc_hc_tx_update_x(...);
> 	}
> 
> Makes sense?

ccid4_hc_tx_x_header_penalty() modifies hctx->ccid4hctx_x. If new x
differs from old x at the end of ccid4_hc_tx_update_x(),
ccid4_update_send_interval() is called. As far as I can see, if we
wanted to have tfrc_hc_tx_update_x(), the caller of that function would
have to deal with changed x by calling *_update_send_interval(), which
is CCID-dependant.

Maybe tfrc_hc_tx_update_x() could update x, return old x, and indeed let
the caller to call ccid4_hc_tx_x_header_penalty(), if wanted, and
finally *_update_send_interval, if necessary. Since
ccid4_hc_tx_update_x() is currently called from two different places, we
could have something like this instead:

static void ccid4_hc_tx_update_x(hctx)
{
	const  __u64 old_x = tfrc_hc_tx_update_x(hctx);
	ccid4_hc_tx_x_header_penalty(hctx);
	if (hctx->ccid4hctx_x != old_x)
		ccid4_update_send_interval(hctx);
}

And respectively:

static void ccid3_hc_tx_update_x(hctx)
{
	const  __u64 old_x = tfrc_hc_tx_update_x(hctx);
	if (hctx->ccid4hctx_x != old_x)
		ccid3_update_send_interval(hctx);
}

Finally, tfrc_hc_tx_update_x() should be trimmed a little:

@@ -198,3 +198,2
-	if (hctx->ccid4hctx_x != old_x)
-		foo_update_send_interval(hctx);
+	return old_x;
 }

Re: [PATCH 6/25] Reduce allowed sending rate by a factor that accounts for packet header size

[Gerrit Renker]

Please see at bottom of message.

| On Thu, Nov 08, 2007 at 10:15:23 +0000, Gerrit Renker wrote:
| > Since ccid4_hc_tx_x_header_penalty() is called in both the if/else
| > branches, it looks to me that you can put it before the if/else. 
| > If you then wanted to abstract this function, it looks as if a wrapper
| > could be used:
| > 
| > 	ccid4_hc_tx_update_x(hctx) 
| > 	{
| >               ccid4_hc_tx_x_header_penalty(hctx);
| > 		tfrc_hc_tx_update_x(...);
| > 	}
| > 
| > Makes sense?
| 
| ccid4_hc_tx_x_header_penalty() modifies hctx->ccid4hctx_x. If new x
| differs from old x at the end of ccid4_hc_tx_update_x(),
| ccid4_update_send_interval() is called. As far as I can see, if we
| wanted to have tfrc_hc_tx_update_x(), the caller of that function would
| have to deal with changed x by calling *_update_send_interval(), which
| is CCID-dependant.
| 
| Maybe tfrc_hc_tx_update_x() could update x, return old x, and indeed let
| the caller to call ccid4_hc_tx_x_header_penalty(), if wanted, and
| finally *_update_send_interval, if necessary. Since
| ccid4_hc_tx_update_x() is currently called from two different places, we
| could have something like this instead:
| 
| static void ccid4_hc_tx_update_x(hctx)
| {
| 	const  __u64 old_x = tfrc_hc_tx_update_x(hctx);
| 	ccid4_hc_tx_x_header_penalty(hctx);
| 	if (hctx->ccid4hctx_x != old_x)
| 		ccid4_update_send_interval(hctx);
| }
| 
| And respectively:
| 
| static void ccid3_hc_tx_update_x(hctx)
| {
| 	const  __u64 old_x = tfrc_hc_tx_update_x(hctx);
| 	if (hctx->ccid4hctx_x != old_x)
| 		ccid3_update_send_interval(hctx);
| }
| 
| Finally, tfrc_hc_tx_update_x() should be trimmed a little:
| 
| @@ -198,3 +198,2
| -	if (hctx->ccid4hctx_x != old_x)
| -		foo_update_send_interval(hctx);
| +	return old_x;
|  }
| 
| -
I agree, you have a valid point here. Maybe I should not have started
this thread, after first suggesting to keep things separate. But I am
guessing that eventually you would like to reduce code duplication, the
above was a start.

Now with regard to the above - we end up having three different
functions doing each a slice of the work and with interleaved calling.

I have another suggestion which I believe may be simpler: The `header
penalty' is just a multiplication applied to X. The sender does not
use X directly, but rather t_ipi = s/X. And it has to compute this
anyway, in update_send_interval(), each time X changes.

I wonder whether the following works, it is in any event much simpler:

 * t_ipi is computed as t_ipi = s / X'
 * the header penalty X' is derived from X as X' = X * s / (s + 36)

Taken together, we have 

	t_ipi = s / X'
	      = s / (X * s / (s + 36))
	      = (s + 36) / X

Thus, the suggestion is to

 * keep update_x the same for CCID3 and CCID4 
 * only change update_send_interval()

This has the added advantage of higher precision than the previous
approach (accumulation of rounding errors). I think it would look like

 /* 
  * Update t_ipi with regard to the header penalty X *= s/(s + 36),
  * which is factored into the t_ipi equation
  */
 hctx->ccid4hctx_t_ipi = scaled_div32(((u64)hctx->ccid3hctx_s +  CCID4_NOM) << 6,
                                             hctx->ccid3hctx_x);

since all the X* quantities are scaled by 2^64 to avoid fixed-point
division problems.

Re: [PATCH 6/25] Reduce allowed sending rate by a factor that

[Tommi Saviranta]

On Fri, Nov 09, 2007 at 15:03:28 +0000, Gerrit Renker wrote:
> Maybe I should not have started this thread, after first suggesting to
> keep things separate. But I am guessing that eventually you would like
> to reduce code duplication, the above was a start.

That's definitely one of the long run goals. While it may not be one of
the top priorities to worry about code duplication, it definitely pays
to give it a thought already.

> Now with regard to the above - we end up having three different
> functions doing each a slice of the work and with interleaved calling.

Actually two functions. There is absolutely no reason why
ccid4_hc_tx_x_header_penalty() should be a separate function. Even now,
there is effectively exactly one place from where it is called. Silly
me.

> I have another suggestion which I believe may be simpler: The `header
> penalty' is just a multiplication applied to X. The sender does not
> use X directly, but rather t_ipi = s/X. And it has to compute this
> anyway, in update_send_interval(), each time X changes.

> Taken together, we have 
> 
> 	t_ipi = s / X'
> 	      = s / (X * s / (s + 36))
> 	      = (s + 36) / X
> 
> Thus, the suggestion is to
> 
>  * keep update_x the same for CCID3 and CCID4 
>  * only change update_send_interval()

> This has the added advantage of higher precision than the previous
> approach (accumulation of rounding errors).

I'm not sure how conservative we want to be about it, but if we take the
header size in account in update_send_interval() only, we do a bit of
unnecessary work when update_send_interval() is called from update_s().
The difference may be insignificant, especially considering higher
precision, which I didn't really think about.

>  /* 
>   * Update t_ipi with regard to the header penalty X *= s/(s + 36),
>   * which is factored into the t_ipi equation
>   */
>  hctx->ccid4hctx_t_ipi = scaled_div32(((u64)hctx->ccid3hctx_s +  CCID4_NOM) << 6,
>                                              hctx->ccid3hctx_x);

Going for higher precision makes perfect sense. However the calculation
is slightly different for CCID 3 and 4, so I think updating
update_send_interval() isn't that simple:

  ccid3_t_ipi = s / x
  ccid4_t_ipi = max((s + CCID4_H) / x, CCID4_MIN_IPI)

I can't see of a good way to share that code between the CCIDs without
bits of extra information in struct tfrc_hc_tx_sock. I think we have
four options:

 * Set CCIDx_H and CCIDx_MIN_IPI in hctx and use them as part of t_ipi
   calculation,
 * set a bit in hctx to decide which equation to use,
 * add function pointer to suitable calculate_t_ipi() to be called from
   tfrc_update_send_interval(), and
 * try a different approach.

The first options is most likely pointless since some unnecessary work
would have to be done for CCID 3. The second option would probably lead
to spaghetti code where everything would eventually depends on that bit,
and shared_tfrc.c would contain lots of code that would in fact belong
to ccidx.c. (Don't get me wrong, I'm really not against this!) The third
option could give quick relief here, but it suffers from the same
problem as option two, although it looks neater at first. Besides that I
have no idea if using function pointers is considered a bad idea in
kernel code.

I don't think there are easy answers to this.

Re: [PATCH 6/25] Reduce allowed sending rate by a factor that accounts for packet header size

[Gerrit Renker]

| > But I am guessing that eventually you would like
| > to reduce code duplication, the above was a start.
| 
| That's definitely one of the long run goals. While it may not be one of
| the top priorities to worry about code duplication, it definitely pays
| to give it a thought already.
| 
Agreed, I think it is useful to keep this discussion running in the
background, but maybe not make it top priority (more below).

| > Now with regard to the above - we end up having three different
| > functions doing each a slice of the work and with interleaved calling.
| 
| Actually two functions. There is absolutely no reason why
| ccid4_hc_tx_x_header_penalty() should be a separate function. Even now,
| there is effectively exactly one place from where it is called. Silly
| me.
No, not at all -- you are making good points here. Discussion is often the
only way to arrive at better code. I have experienced that myself, some of
the best ideas actually came out of discussions with Arnaldo and Ian.

| > I have another suggestion which I believe may be simpler: The `header
| > penalty' is just a multiplication applied to X. The sender does not
| > use X directly, but rather t_ipi = s/X. And it has to compute this
| > anyway, in update_send_interval(), each time X changes.
| 
| > Taken together, we have 
| > 
| > 	t_ipi = s / X'
| > 	      = s / (X * s / (s + 36))
| > 	      = (s + 36) / X
| > 
| > Thus, the suggestion is to
| > 
| >  * keep update_x the same for CCID3 and CCID4 
| >  * only change update_send_interval()
| 
| > This has the added advantage of higher precision than the previous
| > approach (accumulation of rounding errors).
| 
| I'm not sure how conservative we want to be about it, but if we take the
| header size in account in update_send_interval() only, we do a bit of
| unnecessary work when update_send_interval() is called from update_s().
The idea is nice, but how do you want to integrate it with the moving
average in update_s():

	const u16 old_s = hctx->ccid4hctx_s;

        hctx->ccid4hctx_s = old_s = 0 ? len : (9 * old_s + len) / 10;

When writing 

        hctx->ccid4hctx_s += 36,

the header penalty gets `smoothed out' (i.e. is lost) in the weighted 
average. But I think your approach is in essence good - to find the
highest possible abstraction; this is needed for the other work.

| >  hctx->ccid4hctx_t_ipi = scaled_div32(((u64)hctx->ccid3hctx_s +  CCID4_NOM) << 6,
| >                                              hctx->ccid3hctx_x);
| 
| Going for higher precision makes perfect sense. However the calculation
| is slightly different for CCID 3 and 4, so I think updating
| update_send_interval() isn't that simple:
| 
|   ccid3_t_ipi = s / x
|   ccid4_t_ipi = max((s + CCID4_H) / x, CCID4_MIN_IPI)
| 
You have thought ahead and combined both requirements into one: the
above now gives most of the body for a new function
ccid4_update_send_interval(). Combining this with your comments to 
patch 5/25, this would make a nice replacement. Do you or Leandro want
to codify this?


| I can't see of a good way to share that code between the CCIDs without
| bits of extra information in struct tfrc_hc_tx_sock. I think we have
| four options:
| 
|  * Set CCIDx_H and CCIDx_MIN_IPI in hctx and use them as part of t_ipi
|    calculation,
|  * set a bit in hctx to decide which equation to use,
|  * add function pointer to suitable calculate_t_ipi() to be called from
|    tfrc_update_send_interval(), and
|  * try a different approach.
When thinking through this, I found another
   * add a function pointer (*update_intvl)() to update_x() 

<snip>	
| Besides that I have no idea if using function pointers is considered a
| bad idea in kernel code.
My understanding of the kernel coding guidelines is that simplicity and
clarity are a priority (since others need to read the code, too); and
that function pointers are a very useful abstraction technique. But
many function pointers as arguments are probably also not good.

| I don't think there are easy answers to this.
Fully agree. I think that it will be much easier to separate the
functional blocks when you've finished your CCID4 design. Then the
similarities between the new and the old code will be obvious.

I am saying this since I have used the same approach with UDP-Lite, and
found it very useful: in the begin it was utter code duplication, I
literally copy+pasted udp.c into udplite.c, for the whole time the code
was developed. When it became time to submit this for mainline, it was
easy/easier to abstract the difference between UDP and UDP-Lite, and the
result is now quite short. But it was only easy because the related code
was in one unit (not cut into pieces) during development, which helped a
lot.