Consider alternatives for update_shaper_rate

[lynxthecat]

@moeller0 and @patrakov our latest shaper rate adjustment code is:

cake-autorate/cake-autorate.sh

Line 359 in 7350fc0

update_shaper_rate()

update_shaper_rate()
{
	local direction="${1}" # 'dl' or 'ul'

	case "${load_condition["${direction}"]}" in

		# upload Starlink satelite switching compensation, so drop down to minimum rate for upload through switching period
		ul*sss)
			shaper_rate_kbps["${direction}"]="${min_shaper_rate_kbps[${direction}]}"
			;;
		# download Starlink satelite switching compensation, so drop down to base rate for download through switching period
		dl*sss)
			shaper_rate_kbps["${direction}"]=$(( shaper_rate_kbps["${direction}"] > base_shaper_rate_kbps["${direction}"] ? base_shaper_rate_kbps["${direction}"] : shaper_rate_kbps["${direction}"] ))
			;;
		# bufferbloat detected, so decrease the rate providing not inside bufferbloat refractory period
		*bb*)
			if (( t_start_us > (t_last_bufferbloat_us["${direction}"]+bufferbloat_refractory_period_us) ))
			then
				adjusted_achieved_rate_kbps=$(( (achieved_rate_kbps["${direction}"]*achieved_rate_adjust_down_bufferbloat)/1000 )) 
				adjusted_shaper_rate_kbps=$(( (shaper_rate_kbps["${direction}"]*shaper_rate_adjust_down_bufferbloat)/1000 )) 
				shaper_rate_kbps["${direction}"]=$(( adjusted_achieved_rate_kbps > min_shaper_rate_kbps["${direction}"] && adjusted_achieved_rate_kbps < adjusted_shaper_rate_kbps ? adjusted_achieved_rate_kbps : adjusted_shaper_rate_kbps ))
				t_last_bufferbloat_us["${direction}"]="${EPOCHREALTIME/./}"
			fi
			;;
            	# high load, so increase rate providing not inside bufferbloat refractory period 
		*high*)
			if (( t_start_us > (t_last_bufferbloat_us["${direction}"]+bufferbloat_refractory_period_us) ))
			then
				shaper_rate_kbps["${direction}"]=$(( (shaper_rate_kbps["${direction}"]*shaper_rate_adjust_up_load_high)/1000 ))
			fi
			;;
		# low or idle load, so determine whether to decay down towards base rate, decay up towards base rate, or set as base rate
		*low*|*idle*)
			if (( t_start_us > (t_last_decay_us["${direction}"]+decay_refractory_period_us) ))
			then

				if ((shaper_rate_kbps["${direction}"] > base_shaper_rate_kbps["${direction}"]))
				then
					decayed_shaper_rate_kbps=$(( (shaper_rate_kbps["${direction}"]*shaper_rate_adjust_down_load_low)/1000 ))
					shaper_rate_kbps["${direction}"]=$(( decayed_shaper_rate_kbps > base_shaper_rate_kbps["${direction}"] ? decayed_shaper_rate_kbps : base_shaper_rate_kbps["${direction}"]))
				elif ((shaper_rate_kbps["${direction}"] < base_shaper_rate_kbps["${direction}"]))
				then
					decayed_shaper_rate_kbps=$(( (shaper_rate_kbps["${direction}"]*shaper_rate_adjust_up_load_low)/1000 ))
					shaper_rate_kbps["${direction}"]=$(( decayed_shaper_rate_kbps < base_shaper_rate_kbps["${direction}"] ? decayed_shaper_rate_kbps : base_shaper_rate_kbps["${direction}"]))
				fi

				t_last_decay_us["${direction}"]="${EPOCHREALTIME/./}"
			fi
			;;
		*)
			log_msg "ERROR" "unknown load condition: ${load_condition[${direction}]} in update_shaper_rate"
			kill $$ 2>/dev/null
			;;
	esac
        # make sure to only return rates between cur_min_rate and cur_max_rate
        ((shaper_rate_kbps["${direction}"] < min_shaper_rate_kbps["${direction}"])) && shaper_rate_kbps["${direction}"]="${min_shaper_rate_kbps[${direction}]}"
        ((shaper_rate_kbps["${direction}"] > max_shaper_rate_kbps["${direction}"])) && shaper_rate_kbps["${direction}"]="${max_shaper_rate_kbps[${direction}]}"
}

Let's continue the discussion about shaper rate control alternatives from #115 here.

[lynxthecat]

@patrakov copying my post from #115 here:

Would you be able to summarize the rate control logic you tested? I had a very quick look, but it seems a summary would be helpful.

blindly trusts the achieved rate pre-shaper as something that the link definitely can support, even during bufferbloat periods, for the purpose of never setting the shaper below let's say 90% of that

I can't wrap my head around what that means in terms of how the shaper rate is set. Would you be able to copy/paste the code from the update_shaper_rate (formerly get_next_shaper_rate) function?

[lynxthecat]

Also @moeller0 wrote:

Just a reminder: earlier, I proposed a change (now officially rejected) that, for the download direction, blindly trusts the achieved rate pre-shaper as something that the link definitely can support, even during bufferbloat periods, for the purpose of never setting the shaper below let's say 90% of that. @lynxthecat can you compare?

What the current code does is to take the minimum of "current shaper rate * factor1" and "last achieved rate * factor2". Your proposal is to jettison the first term. I think this is wrong, because the achieved rate necessarily measured the past and if say we have a step like reduction from 100 to 10 "speed units" the last achieved rate will (to simplify) 100 which clearly after the step is incorrect... My mental model is we base our decision mainly on the current shaper rate, but that the achieved rate only into account if that would cause a steeper rate reduction... exactly as the achieved rate is be necessity looking into the past.

[patrakov]

I am not a user of cake-autorate anymore, but here is the patch that I used in the past:

diff --git a/cake-autorate.sh b/cake-autorate.sh
index d1f0e5f..366cbf8 100755
--- a/cake-autorate.sh
+++ b/cake-autorate.sh
@@ -309,8 +309,7 @@ get_next_shaper_rate()
 		*bb*)
 			if (( t_next_rate_us > (t_last_bufferbloat_us+bufferbloat_refractory_period_us) )); then
 				adjusted_achieved_rate_kbps=$(( (achieved_rate_kbps*achieved_rate_adjust_down_bufferbloat)/1000 )) 
-				adjusted_shaper_rate_kbps=$(( (shaper_rate_kbps*shaper_rate_adjust_down_bufferbloat)/1000 )) 
-				shaper_rate_kbps=$(( adjusted_achieved_rate_kbps > min_shaper_rate_kbps && adjusted_achieved_rate_kbps < adjusted_shaper_rate_kbps ? adjusted_achieved_rate_kbps : adjusted_shaper_rate_kbps ))
+				shaper_rate_kbps=$(( adjusted_achieved_rate_kbps >= min_shaper_rate_kbps ? adjusted_achieved_rate_kbps : shaper_rate_kbps ))
 				t_last_bufferbloat_us=${EPOCHREALTIME/./}
 			fi
 			;;
@@ -1405,30 +1404,10 @@ fi
 
 # Initialize rx_bytes_path and tx_bytes_path if not set
 if [[ -z "${rx_bytes_path:-}" ]]; then
-	case "${dl_if}" in
-		veth*)
-			rx_bytes_path="/sys/class/net/${dl_if}/statistics/tx_bytes"
-			;;
-		ifb*)
-			rx_bytes_path="/sys/class/net/${dl_if}/statistics/tx_bytes"
-			;;
-		*)
-			rx_bytes_path="/sys/class/net/${dl_if}/statistics/tx_bytes"
-			;;
-	esac
+	rx_bytes_path="/sys/class/net/${ul_if}/statistics/rx_bytes"
 fi
 if [[ -z "${tx_bytes_path:-}" ]]; then
-	case "${ul_if}" in
-		veth*)
-			tx_bytes_path="/sys/class/net/${ul_if}/statistics/rx_bytes"
-			;;
-		ifb*)
-			tx_bytes_path="/sys/class/net/${ul_if}/statistics/rx_bytes"
-			;;
-		*)
-			tx_bytes_path="/sys/class/net/${ul_if}/statistics/tx_bytes"
-			;;
-	esac
+	tx_bytes_path="/sys/class/net/${ul_if}/statistics/tx_bytes"
 fi
 
 if ((debug)) ; then

Of course the change to the get_next_shaper_rate() is wrong - the new logic should have been applied on download only.

[lynxthecat]

I finally tried this, but without having adjusted the other settings the performance was not satisfactory - too much latency let through for too little bandwidth gained. I did try tweaking the achieved_rate_adjust_down_bufferbloat by setting it to 0.8, but this didn't help enough.

I am still open minded that a better approach may exist, and am keen to explore alternatives.

[patrakov]

Could you please be a bit more specific on how much latency and throughout you get with and without the change?

[patrakov]

Also I think that the average throughput is not the right metric to use for evaluation of my patch. Latency - sure, it's (to a reasonable extent) the whole point. For throughput, we should be looking for the percentage of time where the link is wrongly shaped below the acceptable limit for the video chat. In other words, how fast it recovers from short events when it REALLY cannot support the video chat.

[lynxthecat]

Sure, here is a waveform test with the original code:

https://www.waveform.com/tools/bufferbloat?test-id=e1c6f7be-d2c9-47b5-8768-8118f458849c

And one with the adjustment - just ignore upload since I didn't special case that:

https://www.waveform.com/tools/bufferbloat?test-id=99adce61-bf49-447c-bd13-6a47bc0bb421

@patrakov I am keen to explore different options for the rate controller and default settings to see if performance can be improved.

[patrakov]

Thanks for sharing. I guess, for a completely fair comparison, I would also need a waveform bufferbloat test without cake-autorate at all.

But I think now that the change is not applicable to your link. Note that in my setup, I had different settings related to ping rates and rate adjustment factors. With a higher ping rate, cake-autorate on your link recovers by itself much faster than on mine, but, due to the ISP limiting ICMP rates, I cannot afford that.

Regarding the quick recovery, here is what I mean.

Without the change:

Welcome to the whole-company meeting, and, as our internal meeting policy dictates, please turn on your cameras. Does anyone have any urgent items not in the agenda? OK, no such things. The first topic to discuss would be quack quack quack quack quack quack quack quack quack quack quack quack

I.e., perfect until the first bufferbloat event after which it never recovers.

With the change:

Welcome to the whole-company meeting, and, as our internal meeting policy dictates, please turn on your cameras. Does anyone have any urgent items not in the agenda? OK, no such things. The first topic to discuss would be quack quack quack quack quack by Igor. Igor, please keep it short, no more than three minutes total.

Without cake-autorate at all:

Welcome to the whole-company meeting, and, as our internal meeting policy dictates, please turn on your cameras. Does anyone have any urgent items not in the agenda? OK, no such things. The first topic to discuss would be quack quack report... for... the... [multi-second latency!!!] past week by Igor. Igor, please keep it short, no more than three minutes total.

[lynxthecat]

I wonder if the new ewma code I have been experimenting with would help in your case? Now, we retain an ewma of the achieved rate and use that in the controller:

This is with using a pretty conservative alpha (0.2), but a more aggressive alpha might help smooth over temporary drops on your link in achieved rate that are not reflective of connection capacity given burstiness?

[patrakov]

Sounds convincing. I will try later this week on some less-important meeting.

[lynxthecat]

At the moment it's in this branch: https://github.com/lynxthecat/cake-autorate/tree/achieved-rate-ewma.

cake-autorate really is stable now - so hopefully it's now only about focusing on the control aspects.

[moeller0]

The achieved rate ewma is not going to help here. IIRC @patrakov's issue seems to be persistence at the minimum rate, and that happens if the delta delay is too high either sustained or if there are enough latency spikes to keep the controller in reduce-rate condition. The estimated load has likely little to no bearing on the controller's operation in that regime.

[lynxthecat]

But it's also possible that the bufferbloat drops of shaper rate based on achieved rate were sometimes too drastic owing to bursty achieved rate and drops that coincide with the bufferbloat events. If so, the ewma would smooth over such drops, and safeguard against this.