Making Congestion Control Algorithms Insensitive to Underlying Propagation Delays

Recent work [48] provides an in-depth evaluation of how competing popular applications share Internet bandwidth when congested at a common bottleneck, demonstrating that (1) applications do not share bandwidth equally and (2) practical evaluations must consider the full network stack as opposed to settings which isolate the underlying CCA mechanisms in controlled environments. Notably, this prior work equalizes the competing flows’ propagation delays at the bottleneck to focus on how differences in rate achieved between applications was a function of the differences in their workload and chosen mechanisms (CCA, application layer protocols) but not from differences in respective propagation delays.

To illustrate the impact of propagation delay in practical settings, let us run 5 actual Internet experiments in which a YouTube (YT) session (utilizing a variant of BBRv3[14])¹¹1CCA utilized by YouTube reported in [13]. and a OneDrive (1D) session (utilizing Cubic[23]) compete across a 50 Mbps capacity bottleneck with the same moderate sized buffer in all experiments (equivalent to 2BDP assuming 15 ms delay), where the only change across the experiments are the propagation delays experienced by the respective sessions. For 1D, we download the same 5 GB file in each trial. For YT, we play the same video in each trial, selecting the 4k video quality option in YT, preventing the player from down-scaling due to adaptive bit rate logic (we found that YT was still impacted by propagation delay when adaptive bit rate logic is enabled).

To manipulate propagation delay, we introduce a fixed artificial delay at the receiver side – inflating the natural end-to-end propagation delay, allowing us to control delay asymmetrically across competing flows. In this case, we utilize artificial delay on the receiver end to emulate what would occur had the natural propagation delay been larger. We discuss the use of artificial delay to reduce such sensitivity (when applied at the sending side) and the validity of artificial delay in §5.

Each trial consists of an averaging over 4 repetitions, where each repetition is run for 150 seconds – neither YT or 1D finish in this time. The topology of our testbed is included in Figure 1 and additional details on our full application experimental methodology is deferred to §7.3.

Table 1 presents, row-by-row, results for the five distinct trials, each differing by the propagation delays experienced by the applications, as described in columns 2 and 3 for 1D and YT respectively. Performance results include their respective average rates (columns 4 and 5), and an application-level measure of performance for the YT session in terms of total time stalled – including the initial startup delay and all subsequent rebuffering durations during playback (column 6), measured using Selenium web driver [1].

The trials reaffirm that application performance is indeed very sensitive to the propagation delays experienced by the competing flows. As shown in Table 1, Trials 3 and 4 reveal a 32% decrease in rate (from 18.3 to 12.4 Mbps) and a $12\times$ increase in total stall time (from 5.9s to 72.2s)²²2Stall time ranges from 3.5s to 9.1s between repetitions of Trial 3 and from 65s to 86s between repetitions of Trial 4. for the YT session caused solely by a change in propagation delay. The workload and bottleneck are unchanged, but reversing the delay asymmetry between flows causes YouTube’s performance to collapse. Performance across these trials depends not only on the CCAs utilized by the competing applications, but also on their respective workloads, application-layer mechanisms, and any unobservable factors inherent to real-world experiments. However, the qualitative trends observed by comparing performance between these trials mirror those seen in our controlled, CCA-isolated experiments involving a bulk-transfer Cubic flow competing against a bulk-transfer BBR flow under the same bottleneck and propagation-delay conditions. In particular, we observe the the trend of the BBR flow between these settings: when both flows have identical propagation delays, the rate allocated to BBR increases as the common delay increases; when the Cubic flow’s delay is held fixed and the BBR flow’s delay is varied, BBR’s rate increases with its own delay; and when the BBR flow’s delay is held fixed while the Cubic flow’s delay is varied, BBR’s rate increases as the Cubic flow’s delay decreases.

Note a single configuration (i.e., a single trial) is not enough to evaluate how a 1D and YT flow would share a given bottleneck. Before introducing our proposed metric ($\delta$-sensitivity) in §4 and the potential of artificial delay §5, we distill a few key observations from these experiments: (1) Propagation delay significantly impacts performance across heterogeneous applications – even when all other underlying network conditions and workloads remain constant. (2) Properties of RTT-unfairness in homogeneous CCA competition do not always extend to heterogeneous settings; for example, between trials 2 and 4, the rate of 1D (utilizing Cubic) increases when its delay increases despite the dynamics of Cubic flows in homogeneous competition where more bandwidth is conceded to the shorter delayed flow [23]. (3) Equalizing propagation delay between competing applications does not isolate its effect in heterogeneous settings (for instance compare trials 1,2 and 5 where propagation delays across both flows are identical); application mechanisms and CCAs interact with delay in non-trivial ways, and the choice of equalization point itself influences outcomes. (4) Traditional metrics of RTT-unfairness or rate allocation that measure over a single instance (where propagation delays are not varied) fail to capture the variability in quality-of-experience observed in practice.

These observations motivate the need for a new, generalizable approach to quantify and address how sensitive a flow’s performance is to propagation delay, independent of assumptions about fairness or homogeneity.

Define $ℐ=⟨\{f_i\},B⟩$ to consist of $n$ flows $f_1,\mathrm{\dots },f_n$ passing through a bottleneck $B$. Each flow $f_i=(a_i,w_i)$ utilizes congestion control algorithm $a_i\in A$ (where $A$ is the set of heterogeneous CCAs) and carries workload $w_i\in W$ (where $W$ is the set of possible workloads)⁴⁴4The choice to define a flow based on both congestion control algorithm and workload inspired by [55].. The bottleneck $B=(C,\mathrm{\ell },Q)$ is defined in terms of capacity $C$, buffer limit $\mathrm{\ell }$ and queuing discipline $Q$ (e.g FIFO). Note that $ℐ$ fixes a bottleneck, a set of flows through the bottleneck, the utilized CCAs and workloads of each flow without yet specifying the propagation delays assigned to these flows.

We define a propagation delay instance, $D=(d_1,d_2,\mathrm{\dots },d_n)$ to be a specific assignment of propagation delays to these $n$ flows. Armed with both $ℐ$ and $D$, one can model, simulate, or execute the system and determine the resulting rates $r_i=R_i(ℐ,D)$ of each of these $n$ flows when operating in a network setting defined by $ℐ$ and $D$.

$\delta$-sensitivity does not simply consider a single propagation delay instance, but instead is defined over a set $𝒟=\{D\}$ of permissible (to the current setting) propagation delay instances. Each distinct $D\in 𝒟$ will yield its own set of resulting rates, such that $R_i(ℐ,D_1)$ need not equal $R_i(ℐ,D_2)$ for two distinct $D_1,D_2\in 𝒟$. The $\delta$-sensitivity of flow $i$ for the network setting described by $ℐ$ over the set of propagation delay instances $𝒟$ is,

In other words, take this network of flows, sample using different propagation delays drawn from this set $𝒟$ of permissible propagation delay assignments, and for each flow $f_i$ compute the log-ratio⁵⁵5We find the log-ratio more semantically meaningful than a standard ratio because a flow being “insensitive” to delay maps elegantly to $\delta (i)=0$. between the largest and smallest allocations assigned to it across all $D\in 𝒟$. ${\delta }_{ℐ,𝒟}(i)=0$ implies that for the network setting $ℐ$, the rate $r_i$ achieved by flow $i$ is unaffected by changes in propagation delay assignments in the set of propagation delay instances $𝒟$ considered.

$\delta$-sensitivity is intended to apply on a case-by-case basis for a) a given set of flows assigned respectively to specific CCAs with specific workloads through a specific bottleneck link and b) the permissible propagation delay conditions that can be undertaken by those flows. Note that (a) is typical for most evaluations of congestion control protocols whereas (b) allows for variation and comparison across these varied propagation delays, where traditional evaluations often fix flows to specific propagation delays.

The reason for allowing the scenario to define the permissible set of delays that form $𝒟$ is because different networking environments may have different limits on the ranges and variances of permissible propagation delays. For instance, a data center environment might comprise flows which are guaranteed to have similarly low propagation delays with minimal variance [24]; a traditional wide area networking environment might consider a fairly broad range of propagation delays (up to on the order of a few hundred milliseconds) [59]; and space networks [5] might require consideration of delays that are even larger. Furthermore, there are scenarios in which the delays of flows from a content delivery network CDN are consistently small but can interact with competing flows which delays vary greatly.

For concreteness, we give some plausible ways to define the $𝒟$, e.g.,

• $\mathrm{■}$

  Uniform delay range $𝒟=\{(d_1,d_2,\mathrm{\dots },d_n):10\le d_i\le 100\}$: looking only at scenarios where flow propagation delay ranges between 10 and 100.

• $\mathrm{■}$

  Single-flow variation $𝒟=\{(d_1,10,\mathrm{\dots },10):10\le d_1\le 100\}$: looking only at scenarios where all $d_i$ are fixed at 10 except $d_1$ which varies between 10 and 100.

• $\mathrm{■}$

  Symmetric variation $𝒟=\{(d_1,d_2,\mathrm{\dots },d_n):10\le d_0\le 50,d_i=d_0\}$: looking only at scenarios where $d_0$ ranges from 10 to 50 and all $d_i$ equal $d_0$.

Note that $𝒟$ can be defined in such a way that there may be an (exponentially or even infinitely) large set of propagation delay assignments such that it would not be feasible to exhaustively run all configurations to determine the true max and min. We note that experimentally sampling over a subset of configurations provides a lower bound to the delay sensitivity. The observed minimum $m_0$ would upper bound the true minimum ($m_0\ge m$), and the observed maximum $M_0$ would lower bound the true maximum ($M_0\le M$), such that $\log (M_0/m_0)\le \log (M/m)$.

Figure 3 shows experimental evidence of our intuitive claim that added delay on packet acknowledgments will not implicitly hurt application data latency (i.e., the ability to perform timely data delivery from sender to receiver). This experiment is setup with a socket application that sends a packet every 1ms containing the timestamp of exiting the sending host’s application layer and data is taken upon the receiver processing the packet at the application level. The solid blue line shows the duration of time (in milliseconds) until the receiving application processes the data packet and the dotted line is the duration until the acknowledgment for the packet reaches the sender (completing the total network RTT).

These experiments are intended to represent the perspective of an application that values real-time data transfer. The two hosts are placed on different floors of the same building with an average 1ms delay from sender to receiver and 3ms total RTT. There are four places where delay can be added: sender ingress (ACK delay ${\lambda }^{add}$), sender egress (packet delay), receiver ingress (packet delay) and receiver egress (ACK delay ${\beta }^{add}$). The results of adding 60ms of artificial delay at these four locations support our claim that compared to the baseline of no added delay, delaying acknowledgments at either the sender (${\lambda }^{add}$) or receiver (${\beta }^{add}$) inflates the perceived RTT without hurting sender to receiver latency. Delaying data packets has the obvious result in delaying sender to receiver latency.

These experiments are run over a network path with a capacity that exceeds the rate required by the application with minimal competition from competing streams. Because of this, there is negligible difference between running this application with Cubic or BBR. This shows that in ideal un-congested network scenarios, the addition of 60ms artificial delay does not degrade application performance even when the natural propagation delay is small (only 3ms) and artificial delay is large (60ms). When there is congestion, the choice of CCA has major performance implications and the use of intentional artificial delay becomes relevant.

The purpose of introducing artificial delay is to remove the impact of propagation delay on how competing flows interoperate. This method is most suitable when the introduced artificial delay does not meaningfully degrade an uncontested flow’s performance. Using $\delta$-sensitivity, we can identify such cases: if a flow shows low $\delta$-sensitivity over a delay range $𝒟$ in an uncontested network setting, then artificially inflated delays that remain within $𝒟$ has little impact when the flow is operating alone and is thus a suitable tool for reducing $\delta$-sensitivity when flows compete. For example, 50ms of artificial delay can have negligible impact on file download time when a flow is bottlenecked alone but significant impact when the capacity of the bottleneck is shared with competing traffic. Conversely, 50 ms of artificial delay could have negative impact on short-lived flow such as loading a web-page and negligible impact on reducing $\delta$-sensitivity in settings where this flow competes.

Requiring existing CCAs to immediately incorporate artificial delay can be non-trivial. As an alternative (perhaps temporary, perhaps permanent) to induce artificial delay without changing the underlying structure of the network or the kernel’s implementation of TCP, we propose a simple method to “trick” the CCA into thinking there are $\lambda$ milliseconds of propagation delay by having the sender, artificially delay its own processing of packet acknowledgments (use ${\lambda }^{add}$). When $\lambda$ is larger than any naturally occurring propagation delay, receiver attempts to delay their ACKs will either be subsumed within $\lambda$, cause reduced $\delta$-sensitivity, or can be easily identified as greatly exceeding $\lambda$ (and hence cannot be naturally occurring).

In order to achieve $\lambda ms$ propagation delay, we use an estimate $\widehat{d}$ of minimum propagation delay $d$ and then adjust added proxy delay, ${\lambda }^{add}$, to maintain $\lambda ={\lambda }^{add}+\widehat{d}$. This way, the total propagation delay estimate will be $\lambda$ milliseconds irrespective of actual propagation delay.

The proxy protocol (Algorithm 1) repeatedly checks the minimum RTTs⁷⁷7This procedure is based on how BBR[12] estimates propagation delay. The measure of minrtt can be attained via Linux kernel socket statistics [2] independent of utilized CCA, although measurement errors may be more likely with buffer-filling CCAs (discussed in Section 7.2). to maintain that it is $\lambda$ ms, making adjustments if necessary. We apply added delay ${\lambda }^{add}$ by placing a netem [25] queue at the sender’s ingress port for the connection. This delays packet acknowledgments at the sender before entering the transport layer and being processed by the sender’s CCA. In situations where all competing flows have enabled the $\lambda$-proxy mechanism, no flow has an RTT advantage and all RTT-defined aspects of the CCA’s design and approach to congestion will be equalized between flows.

With an accurate estimate of propagation delay $d$, $\lambda$-proxy ensures zero $\delta$-sensitivity for $𝒟=\{(d_1,\mathrm{\dots },d_n):d_i\le \lambda \}$ if all competing flows enable the proxy. Compared to the difficulty of estimating queuing delay and network capacity, we find that propagation delay can be estimated consistently and accurately with increased accuracy for longer lived flows. We set $\lambda$ at 100ms for all of our proxy experiments in §6.

In this subsection, we demonstrate an important phenomenon of CCAs such as Copa[7], Vegas[8], PCC[16, 17], and Libra[37] whose design aims to converge to unique equilibrium fixed points that do not depend on the individual flow’s propagation delay (i.e., their $\delta$-sensitivity is close to 0). We will show that when these flows compete across a bottleneck with alternate CCAs, then variations in their flow propagation delay (and not necessarily variations in the competing CCA’s propagation delay) do in fact significantly alter their convergence points (i.e., their $\delta$-sensitivity is no longer close to 0).

Our demonstration utilizes ns-3 simulation with an implementation of Copa and BBR [52] in a simple heterogeneous network setting ${ℐ}_{het}$ where two Copa flows, $f_1$ and $f_2$ send data over a 50Mbps bottleneck that is shared by a BBR flow $f_3$ which is is intended to emulate a video streaming application that has a maximum sending rate of 20Mbs [48]. Limiting the video flow (BBR) flow ensures that at least 30Mbps of available capacity is reserved for the two Copa flows. In the comparable homogeneous network setting ${ℐ}_{hom}$ which does not include the BBR flow, the two Copa flows consistently converge to identical rates independent of differences in their propagation delays. Figure 6 demonstrates sensitivity that occurs in the heterogeneous setting ${ℐ}_{het}$ considering $𝒟=\{(d_1,d_2,5)\}$ with $d_1,d_2\in \{20,80\}$, i.e., Copa flow propagation delays of the two flows are any sampling of 20 and 80ms, and the BBR flow has propagation delay of 5ms.⁸⁸8We are focusing on how Copa’s $\delta$-sensitivity is affected by heterogeneous network settings: it is sufficient to show this with a single BBR where the different $D\in 𝒟$ need not even vary the BBR flow’s propagation delay. Each plot shows goodput achieved over time for a given $D\in 𝒟$. The first Copa flow ($f_1$) is plotted with a dashed line and starts 3 seconds before the other Copa flow $f_2$ which is plotted with a solid line. The rate limited BBR flow starts last and is plotted with a dotted gray line. When the two Copa flows have different propagation delays, they exhibit delay sensitivity with 19.7 vs 9.6Mbps and 21.0 vs 8.7Mbps average goodput achieved by the 80ms vs 20ms flow respectively. From these experiments we find ${\delta }_{{ℐ}_{het},𝒟}(i)\ge 1.3,i=1,2$. From experiments not shown in the figure we find Copa’s sensitivity in the comparable homogeneous setting to be ${\delta }_{{ℐ}_{hom},𝒟}(i)\approx 0,i=1,2$.

A second important observation is that in a heterogeneous environment, when the Copa flows have identical propagation delays $𝒟=\{(d,d,5)\}$ there is negligible $\delta$-sensitivity, even when interacting with a flow that utilizes a different CCA (in this case BBR). For instance, with this restriction, ${\delta }_{{ℐ}_{het},𝒟}(2)=0.19$. This importantly shows that the $\delta$-sensitivity exhibited by Copa is with respect to variation of delay across the Copa flows. In other words, just having an additional CCA sharing the bottleneck (without changes to its propagation delay) significantly increases the $\delta$-sensitivity of the Copa protocol when propagation delay variations are only among the Copa flows! While this phenomenon is demonstrated using Copa, the insight applies more generally across CCAs.

The goal of introducing artificial delay is to equalize propagation delays among competing flows to neutralize $\delta$-sensitivity without requiring complex mechanisms implemented in the CCA, as demonstrated with the proxy in §6. In this section, we consider the robustness of this method by demonstrating that even naive approaches to adding artificial delay with errors in reaching the point of equalization can still reliably reduce $\delta$-sensitivity and improve consistent performance.

The naive approach to introducing artificial delay is to add a constant fixed delay to all senders ${\lambda }^{add}$ regardless of the naturally occurring propagation delay of the flow. With this method, any difference in natural propagation delays remains but the relative difference reduces leading to a reduction in $\delta$-sensitivity. In other words, a flows sensitivity to the delay range $𝒟$ can be reduced solely by uniformly adding ${\lambda }^{add}$ to all delays.

To demonstrate this phenomenon we run experiments between four competing flows utilizing four different CCAs in an emulated test-bed following that used in §6. Figure 7(a) plots the $\delta$-sensitivity of each of the four flows managed by BBRv3, Hybla, Cubic, and Reno when congested by a single 100 Mbps capacity bottleneck over the range of delays $𝒟=\{10\text{ms}\le d_i\le 30\text{ms}\}$ without adding artificial delay (left) and then with 50ms of added delay (right). By adding 50ms of artificial delay, the range $𝒟$ that the flows operate over effectively becomes $𝒟=\{60\text{ms}\le d_i\le 80\text{ms}\}$. By reducing the proportional difference of asymmetric delay, the $\delta$-sensitivity of all four flows is reduced.

Next, we demonstrate that $\delta$-sensitivity is reduced by attempting to equalize propagation delays between competing flows even when the intended point of equalization is missed due to inaccurate estimates of the naturally occurring propagation delays. When all competing flows utilize buffer-filling loss-based CCAs, for example, it may be more difficult to make estimates of the underlying propagation delay without introducing additional mechanisms to make such estimates. Figure 7(b) shows the sensitivity of four competing flows managed by CCAs Illinois[35], Westwood[38], Cubic, and Reno when congested at a 100 Mbps bottleneck over range of delays ${𝒟}_1$ ranging from 5ms to 30ms, and ${𝒟}_2$ ranging from 35ms to 45ms to emulate scenario where the agreed upon point of equalization was 40ms with estimation errors of $\pm 5$ms. By artificially altering the delay range from ${𝒟}_1$ to ${𝒟}_2$, each flow’s $\delta$-sensitivity is reduced to less than 1, significantly improving performance consistency.

In this section, we return focus to popular application performance in practical settings and use $\delta$-sensitivity to demonstrate that delay-induced unpredictability remains a significant impediment to predictable performance. As the sending hosts of popular applications are out of our control, we use artificial delay at the receiver end to control competing flow propagation delay.