# Optimal Congestion Control for Time-Varying Wireless Links

Prateesh Goyal  Microsoft ResearchUSA ,  Mohammad Alizadeh  MIT CSAILUSA and
Thomas E. Anderson  University of WashingtonUSA

###### Abstract.

Modern networks exhibit a high degree of variability in link rates. Cellular
network bandwidth inherently varies with receiver motion and orientation,
while class-based packet scheduling in datacenter and service provider
networks induces high variability in available capacity for network tenants.
Recent work has proposed numerous congestion control protocols to cope with
this variability, offering different tradeoffs between link utilization and
queuing delay. In this paper, we develop a formal model of congestion control
over time-varying links, and we use this model to derive a bound on the
performance of any congestion control protocol running over a time-varying
link with a given distribution of rate variation. Using the insights from this
analysis, we derive an optimal control law that offers a smooth tradeoff
between link utilization and queuing delay. We compare the performance of this
control law to several existing control algorithms on cellular link traces to
show that there is significant room for optimization.

##  1\. Introduction

Traditional end-to-end congestion control algorithms for computer networks
combine two orthogonal ideas into a single mechanism. The first is to discover
the capacity of the path to carry traffic through probing (Jacobson88, ), and
the second is to respond to congestion in a way that approximates fairness
with respect to how the link is shared (jain1996congestion, ). Provided that
traffic flows persist over multiple round trips (homa, ), and the network
provides timely and regular feedback to endpoints (xcp, ; rcp, ), a number of
practical algorithms exist that can achieve both low queuing delay and high
throughput (homa, ; hpcc, ; swift, ).

Figure 1. Variations in link capacity for a sample Verizon LTE link.

Increasingly, however, modern networks pose a third challenge: path or link
capacity itself is variable on a fine-time scale. For example, in cellular
networks, changes in receiver orientation can cause available bandwidth to
oscillate up or down by a factor of two within a few seconds (sprout, ). Fig.
1, a sample trace from an LTE network, illustrates this effect. Class-based
packet scheduling for virtual networks induces similar behavior. To isolate
different types of customers from each other, network switches can assign
traffic from different virtual networks to different queues, with different
scheduling weights or priorities given to each queue. Whether traffic in other
classes is present or absent can have a large effect on observed network
capacity within the virtual network. Because of the inherent delay in
transmitting information about network state, link variability means that the
endpoint must guess the capacity of the network in the near future, and will
often guess wrong. This can lead to link underutilization (if the capacity is
underestimated) or excess queuing (if it is overestimated).

A number of recent research papers have attempted to adapt traditional
congestion control to this new setting (abc, ; goyal2017rethinking, ; verus, ;
sprout, ; pbe_cc, ; copa, ; pcc, ; bbr, ). These protocols differ from each
other in many aspects; in particular, which _feedback signals_ are used by the
sender and the exact _control law_ to adjust the sending rate. Fig. 2 shows
the performance of various schemes on a sample Verizon LTE trace, reproduced
from earlier work (abc, ). While several schemes lie on what appears to be the
Pareto frontier, there is no clear winner: different schemes provide different
tradeoffs between underutilization and delay. Thus, we must pick different
algorithms and protocols depending on how much we value each goal. Low
queueing reduces short request latency; high throughput benefits longer
requests.

Figure 2. Performance of existing schemes on a Verizon LTE trace. The
experiments consist of a single long-running flow. Numbers are from (abc, ).
The dashed red line represents the Pareto frontier of performance.

In this paper, we step back and ask a more fundamental question. Is there a
bound on the optimal performance for congestion control over time varying
links based on the statistical properties of the variation. To make this
problem tractable, we reduce the setting to the simplest imaginable: a single,
long-lived flow over a time-varying link that changes only once per round trip
according to a simple Markov process (howard1960dynamic, ) (with restrictions
on the transition probabilities). For each round trip, the link capacity
differs from the previous round trip by a multiplicative I.I.D. random
variable factor. We show that it is possible to derive a bound for this case
analytically. The bound is a function of the uncertainty in link capacity at
the sender: the more uncertain the link, the worse the bound.

We can then ask, for this simplified model of real network links, is it
possible to achieve this bound? We show that the answer is yes, provided the
link variability is small. For the more general case, we formulate the
congestion control task as a Markov Decision Process (sutton2018reinforcement,
) (MDP) to derive an optimal control law for time-varying links.
Interestingly, the structure of this optimal control law is quite different
from the control laws used by much of the previous work in congestion control
for time-varying links. In particular, the optimal sending rate is unrelated
to the previous sending rate, but depends only on the previous link capacity
and queue occupancy. This control structure allows us to smoothly trade
queuing delay for better utilization across a broad range. We then extend our
analysis to prove an optimal control law for the case where the link
variability is predictable in some manner (e.g., using machine learning or
other knowledge). Finally, we consider scenarios where the link variability
has a more general Markov structure with few restrictions on the transitions.

Note that our models are simplifications, and real wireless links need not
follow the models we use. Our goal is not to construct perfect models for link
capacity based on the specifics of the link and the physical layer. Instead,
we present general and tractable models to capture key components of
variability in link capacity on the scale of the round trip delay, draw
insights, and show that these insights can translate to performance
improvements. We use real cellular traces to validate our findings.

###  1.1. Key Findings

Figure 3. Transition diagram for different models of link capacity.

To capture variations in the link capacity, we develop three discrete-time
Markov chain models for the link capacity with increasing complexity. Fig. 3
shows the schematics for the three link models we consider in this paper. For
each model, we establish that there is a _fundamental_ bound on congestion
control performance in terms of expected link underutilization and queuing
delay (Theorem 1, Corollary 7 and Theorem 1) , and we derive the optimal
congestion control law (Theorem 4, Corollary 8 and 5).

Multiplicative I.I.D. Factors (MIF) model (§4): We begin by analysing a basic
model for variations in link capacity. The analysis of this model is easy to
follow yet the model is still expressive enough to provide insights that
improve performance on real-world cellular traces. Later, we will use the
basic analysis framework we establish for this model to extend our analysis to
more comprehensive models. In this model, the link capacity at time step $t$
($\mu(t)$) is dependent on the capacity in the previous round trip
($\mu(t-1)$) as follows,

(1) $\displaystyle\mu(t)=\mu(t-1)\cdot X_{t},$

where $X_{t}$ are I.I.D random variables. Under the assumptions of the model,
the optimal control law is of the simple form,

(2) $\displaystyle s(t)=\left(C\cdot\mu(t-1)-\frac{Q(t-1)}{T}\right)^{+},$

where $T$ is the base round trip time (RTT), $Q(t)$ is the queue size. $C$ is
a positive constant that depends on the desired trade-off between
underutilization and queuing delay, and characteristics of the random variable
$X$.

This control law is interesting for several reasons. First, in several end-to-
end schemes (verus, ; sprout, ; copa, ; cubic, ), the current link capacity is
not signalled back to the sender. Instead, the sender has to infer the link
capacity indirectly. Such inference might have errors (abc, ), and these
errors can lead to poor performance. Second, in existing explicit signalling
protocols111Explicit protocols directly signal congestion or rate information
to endpoints from routers. such as XCP (xcp, ) and RCP (rcp, ), the sending
rate is derived iteratively based on the sending rate in previous rounds. The
prototypical control law adjusts the sending rate up/down by increments that
depend on a congestion signal fed back by the routers. By contrast, our
analysis shows that the optimal controller does not depend on the prior
sending rate but only on the link capacity and queuing in the previous round.
If in a given round, we guess wrong (as we must from time to time), we should
not compound that error by basing our new sending rate on the old erroneous
one. Finally, to adjust the trade-off in underutilization and delay, this rule
argues for only changing the constant $C$ and keeping the queuing penalty term
the same. In contrast, protocols like ABC (abc, ) incorrectly treat $C$ as a
“target utilization”, setting it to a value close to one and adjusting the
queuing penalty term to achieved a desired performance trade-off. We show that
is not optimal. In our evaluation over real cellular traces, our optimal
control law outperforms these existing schemes.

Prediction-based Multiplicative I.I.D. Factors (PMIF) model (§4.4): Next, we
consider scenarios where the sender has access to an imperfect prediction
($Pred(t-1)$) about the current link capacity ($\mu(t)$). The uncertainty in
link capacity at the sender is governed by the following equations:

(3) $\displaystyle\mu(t)$ $\displaystyle=Pred(t-1)\cdot X^{p}_{t},$
$\displaystyle Pred(t)=Pred(t-1)\cdot X^{pred}_{t},$

where $X^{p}_{t}$ and $X^{pred}_{t}$ are I.I.D random variables. In other
words, prediction error is structurally similar to the error induced by
feedback delay in the MIF model. A corollary from the analysis of the MIF
model is that the optimal control law in this new model is of the form,

(4) $\displaystyle s(t)=\left(C^{p}\cdot
Pred(t-1)-\frac{Q(t-1)}{T}\right)^{+},$

where $C^{p}$ is a positive constant that depends on the desired performance
trade-off and characteristics of $X^{p}$ and $X^{pred}$. We find that a good
predictor for link capacity can substantially improve performance on cellular
traces. Thus, a promising future direction is to design algorithms to predict
link capacity for time-varying wireless links, e.g., using physical layer
information (predictwifi, ).

State-dependent Multiplicative Factors (SMF) (§6): Finally, we relax the
constraints in the MIF Model for how capacity changes between each time step.
We assume a generic Markov chain for how the underlying link state governing
the link capacity (depicted by $S(t)$) evolves. In particular, the link state
is a set that includes the current link capacity and any other quantities that
might impact the link capacity in the next round trip. In this model, the
uncertainty in link capacity at the sender ($\mu(t)$) is governed by the link
state in the previous round trip ($S(t-1)$). The optimal control law is of the
form,

(5) $\displaystyle
s(t)=\left(C^{S(t-1)}\cdot\mu(t-1)-\frac{Q(t-1)}{T}\right)^{+}$

where S represents the space of all possible states $S(t)$, and,
$C^{k},\forall k\in\textbf{S}$ is a positive constant that depends on the
probability transition matrix for the link state. Compared to the MIF Model,
this model is more realistic as it does not restrict the relative uncertainty
in the link capacity to be the same in every round and allows for the
uncertainty to be dependent on the underlying link state. For example, the SMF
model (but not the MIF model) allows there to be a minimum and maximum
capacity. As expected, on cellular traces, the control law above improves
performance over the (simpler) control law based on the MIF model.

##  2\. Related Work

Queueing Theory: A substantial body of work in the field of queuing theory
pertains to analyzing the dynamics of queues in computer systems
(kleinrock1976queueing, ). Existing techniques are useful for analysing
systems in steady state equilibrium where both the rate of arrival of jobs and
the job size can be modeled as probabilistic processes (e.g., as Markovian
chains). An important characteristic of our work is that the queue service
rate is variable with time. A branch of queuing theory considers time-varying
behavior as an exception to steady state analysis. Some work has focused on
modelling time-varying arrival rates, e.g., as a way to model diurnal customer
requests (massey, ). Time-varying service rates have also been considered for
the case where the number of servers scales up to meet increased demand (tvq,
). By contrast, the service rate of a cellular link is endogenous, with
variation that is largely independent of the workload demand. Thus, even
though the link rate is time varying, we can analyse it as a steady state
Markov process. Cecchi and Jacko (tvwifi, ) develop a general Markov model,
similar to our SMF model, for representing changes in wireless transmission
capacity. Their focus is on studying multi-user fairness for media access
rather than congestion control.

Analysis of real-world congestion control protocols: This is a crowded space
with a lot of work spanning theoretical modeling (chiu1989analysis, ;
mathis1997macroscopic, ), experimental analysis (hock2017experimental, ;
yan2018pantheon, ), and recently formal verification (arun2021toward, ;
nsdi_rw_tcp_bugs, ). While prior work can be used for analysing the
performance of a particular congestion control protocol, they cannot be used
to reason about the performance space of all congestion control laws or to
deduce the optimal control law itself. Moreover, the theoretical analysis in
existing works is primarily for wired links with relatively fixed
capacity.222Some works do allow for minor variations in link capacity to
account for networks components such as token bucket filters (arun2021toward,
). In contrast, we use Markovian models to capture the time-varying nature of
the wireless link.

Existing congestion control protocols: We can classify existing protocols
based on the feedback signals used. Cubic (cubic, ), TCP Reno (newreno, ),
Sprout (sprout, ), Verus (verus, ), and Copa (copa, ) use traditional feedback
signals such as end-to-end delay, packet drops and explicit congestion
notification (ECN) marks (with various active queue management (AQM) schemes
such as CoDel (CoDel, ), PIE (pie, ), and RED (red, ) to mark the ECN) as a
basis to adjust rates. These signals are good for inferring congestion to
reduce the sending rate. However, when the link is underutilized these signals
do not offer much information about the current link capacity. In such cases,
the sender has to resort to a blind increase which can cause poor performance
on time-varying links (abc, ). Explicit congestion control protocols (xcp, ;
rcp, ; abc, ; hpcc, ) where the bottleneck router explicitly communicates a
rate to the sender based on the link capacity can overcome this limitation.
These protocols also differ from each other in the control law they use to
adjust the rate (see §5.1). For cellular networks, some recent work
(xie2015pistream, ; lu2015cqic, ; pbe_cc, ) proposes techniques for leveraging
physical layer information at the sender to compute link capacity without any
explicit feedback from the base station.

##  3\. Preliminaries

Model. We study a discrete-time model of a single long-lived flow transmitting
data on a link with time-varying capacity. Each discrete time step (or
“round”) corresponds to one base round trip time, $T$, defined as the minimum
possible round trip time (RTT) in the absence of queuing delay. Let $\mu(t)$
and $Q(t)$ denote the link capacity and queue length in time step $t$. At the
start of time step $t$, the sender receives feedback about the state of the
system in the previous time step, i.e. $\mu(t-1)$ and $Q(t-1)$. It then
selects a non-negative sending rate, $s(t)$, which it uses throughout time
step $t$. Consequently, the queue length evolves according to:

(6) $\displaystyle Q(t)$ $\displaystyle=(Q(t-1)+s(t)\cdot T-\mu(t)\cdot
T)^{+},$

where $y^{+}=max(0,y)$. We assume $Q(0)=0$.

We make several simplifying assumptions to keep the analysis tractable. First,
our model ignores sub-RTT dynamics, since all network feedback and congestion
control decisions occur at the beginning of each time step. Second, we assume
that the bottleneck router has unlimited buffer space and never drops packets.
Third, we focus on explicit congestion control mechanisms, where the
bottleneck router provides direct feedback about its state to the sender in
each time step. Studying explicit schemes is natural because our goal is to
determine performance bounds on achievable performance for any congestion
control algorithm. Since explicit schemes have more information, any bound for
these schemes also applies to approaches that must infer link conditions from
end-to-end signals like packet loss and delay.

Although we focus on the single-flow case, our analysis extends to settings in
which multiple long-lived flows with the same base round trip time share a
bottleneck link. In such cases, $s(t)$ refers to the aggregate sending rate
across all the senders.

Metrics. Define $q(t)$ as the ratio of the queue length to the link capacity
in time step $t$. The evolution of $q(t)$ is governed by:

(7) $\displaystyle q(t)$
$\displaystyle\triangleq\frac{Q(t)}{\mu(t)}=\frac{(Q(t-1)+s(t)\cdot
T-\mu(t)\cdot T)^{+}}{\mu(t)}.$

$q(t)$ represents the time that it would take to drain the last packet in the
queue at time step $t$, assuming the link capacity stays constant at $\mu(t)$
until the packet departs. Since the link capacity is time-varying, $q(t)$ may
differ from the actual delay experienced by the last packet in the queue at
time step $t$. Nevertheless, it provides an approximate measure of the
instantaneous queuing delay at time $t$, and henceforth we will refer to
$q(t)$ as the queuing delay.

We define the link underutuilization, $U(t)$, as the ratio of the unused
capacity to the available link capacity in time step $t$. The link transmits
$\min\\{s(t)\cdot T+Q(t-1),\mu(t)\cdot T\\}$ worth of data in time step $t$.
Therefore the underutilization in time step $t$ is given by:

(8) $\displaystyle U(t)$ $\displaystyle\triangleq\frac{(\mu(t)\cdot
T-s(t)\cdot T-Q(t-1))^{+}}{\mu(t)\cdot T}.$

Finally, we define the average underutilization ($\bar{U}(t))$) and the
average queuing delay ($\bar{q}(t)$) as follows:

(9) $\displaystyle\bar{U}(t)$ $\displaystyle=\frac{\sum_{i=1}^{t}U(i)}{t},$
$\displaystyle\bar{q}(t)=\frac{\sum_{i=1}^{t}q(i)}{t}.$

We will use $\bar{q}(t)$ and $\bar{U}(t)$ as our main performance metrics in
this paper. Specifically, we will assume that the goal for any congestion
control protocol is to achieve low average queuing delay and low average
underutilization according to the above definitions.

Algorithms. In our analysis, we will only consider causal congestion
protocols.

###### Definition 0.

Causal Congestion Control protocols— A congestion control protocol is
considered causal if, the sending rate in time step $t$, is only dependent on
observations of the system (e.g., link capacity, queue size, etc.) in earlier
time steps.

Causal congestion control protocols decide the sending rate based on past
observations. Note that causal congestion control protocols also include
randomized protocols where the sending rate is not-deterministic.

##  4\. A Simple Link Model

We begin with a simple model where $\mu(t)$ deviates from $\mu(t-1)$ by an
I.I.D. multiplicative factor. We refer to this as the Multiplicative I.I.D.
Factors (MIF) model. Our analysis of the MIF model forms the basis for
studying more complex link models later in the paper.

Formally, $\mu(t)$ evolves according to:

(10) $\mu(t)=\mu(t-1)\cdot X_{t},$

where $X_{t}$ is a I.I.D random variable with probability density function
(PDF) $f(\cdot)$. Since we don’t want the link capacity to drop below zero, we
assume that $X_{t}$ is positive. The link capacity evolution is independent of
the sending rate decisions of the congestion control algorithm, formally,
$X_{t}$ is independent of $Q(i)$, $\mu(i)$ and $s(i),\forall i<t$.
Additionally, independence of $s(t)$ and $X_{t}$ follows from the assumption
that the congestion control algorithm is causal and does not have advanced
knowledge of future capacity variations (although it is permitted to know the
distribution of the variations).

We will first establish a performance bound in terms of the expected
underutilization ($E[\bar{U}(t)]$) and expected queuing delay
($E[\bar{q}(t)]$) that can be achieved by any causal congestion control
algorithm. We use this analysis to draw insights about the optimal congestion
controller for this setting (§4.2). Next, we will derive the exact optimal
control law by posing the problem of deciding the sending rate as a Markov
Decision Process (MDP) (§4.3). In §4.4, we will consider an extension of the
MIF model where the sender can predict the current link capacity with certain
accuracy. We will derive the performance bound and the optimal control law for
this extension. Finally, in §5, we will discuss the implications of our
analysis and validate our findings using real-world cellular traces.

###  4.1. Performance Bound

###### Theorem 1.

In the MIF model, for any causal congestion control protocol and any
$t\in\mathbb{N}$, the point $(E[\bar{q}(t)]$, $E[\bar{U}(t)])$ always lies in
a convex set $\mathbb{C}^{f}\triangleq\\{(x,y)|y\geq g^{f}(x)\\}$, where
$g^{f}(\cdot)$ is defined as follows:

(11) $\displaystyle x$
$\displaystyle=T\cdot\int_{0}^{b}\left(\frac{b}{a}-1\right)\cdot f(a)\cdot
da,$ $\displaystyle g^{f}(x)$
$\displaystyle=\int_{b}^{\infty}\left(1-\frac{b}{a}\right)\cdot f(a)\cdot da,$

where $b\in\mathbb{R}^{+}$.

The curve $g^{f}(\cdot)$ forms the boundary of the set $\mathbb{C}^{f}$. Any
causal congestion control strategy cannot achieve better performance in
expectation than the feasible set $\mathbb{C}^{f}$. Note that in a particular
run (i.e., for a given $\cup_{i=0}^{t}\\{\mu(i)\\}$), a scheme might get lucky
and achieve performance $(\bar{q}(t),\bar{U}(t))$ that lies outside
$\mathbb{C}^{f}$ (i.e. below $g^{f}(\cdot)$), however, in expectation the
performance is bounded by $\mathbb{C}^{f}$.

Figure 4. Trade-off between underutilization and queuing delay, for
$X\sim\textit{U}(0.27,2)$, $T=0.1$s — The grey region presents that feasible
region of any congestion control protocol. The color of the performance bound
($g^{f}(\cdot)$) corresponds to different value of $b$ in Eq. (11).

Figure 5. Trade-off is dependent on the PDF $f$ — The performance bound
becomes worse (further up and to the right) as the extent of link rate
variation increases.

The performance bound depends on the distribution $f$ of the multiplicative
factors $X_{t}$. Fig. 5 shows this performance bound and the feasible region
for a particular distribution. The distribution $f$ captures the uncertainty
about the future link rate at each time step. If $X_{t}$ is highly variable,
then the link rate $\mu(t)$ is highly uncertain (even with knowledge of
$\mu(t-1)$). Our bound quantifies how this uncertainty imposes a limit on the
achievable performance of any congestion control algorithm. For example, Fig.
5 shows the performance bound for two uniform distributions with different
ranges. The more variable distribution imposes a worse bound on performance,
shifting it upwards and to the right.

####  4.1.1. Proof

We first define a new quantity $\rho(t)$ in terms of $Q(t-1)$, $s(t)$ and
$\mu(t-1)$ as follows,

(12) $\displaystyle\rho(t)=\frac{\frac{Q(t-1)}{T}+s(t)}{\mu(t-1)}.$

In time step $t$, the total amount of data available (that can be serviced) at
the link is $Q(t-1)+T\cdot s(t)$. Thus, $\rho(t)$ can be thought of as the
“load” on the link in time step $t$ relative to the link capacity in previous
time step $\mu(t-1)$. With this new quantity, using $\mu(t)=\mu(t-1)\cdot
X_{t}$, we can simplify Equations (7) and (8) as follows:

$\displaystyle q(t)$ $\displaystyle=\frac{(Q(t-1)+s(t)\cdot T-\mu(t)\cdot
T)^{+}}{\mu(t)}=T\cdot\left(\frac{\rho(t)}{X_{t}}-1\right)^{+},$ (13)
$\displaystyle U(t)$ $\displaystyle=\frac{(\mu(t)\cdot T-s(t)\cdot
T-Q(t-1))^{+}}{\mu(t)\cdot T}=\left(1-\frac{\rho(t)}{X_{t}}\right)^{+}.$

Notice that both $q(t)$ and $U(t)$ depend only on $\rho(t)$ and the value of
the random variable $X_{t}$. Moreover, $\rho(t)$ itself is a random variable
dependent on $Q(t-1)$, $\mu(t-1)$, and the congestion control strategy (which
selects $s(t)$). Crucially, $\rho(t)$ and $X_{t}$ are independent. We now use
this independence to establish a bound on the expected underutuilization and
queuing delay for a single time step $t$. But first, we need the following
Lemma showing that the function $g^{f}$ is convex.

###### Lemma 0.

The function $g^{f}(\cdot)$ and the set $\mathbb{C}^{f}$ are convex for any
positive PDF function $f$, where $f(x)=0$ for all $x\leq 0$.

###### Proof.

See Appendix D.1. ∎

To compute $E[q(t)]$ and $E[U(t)]$, we will first condition on the value of
$\rho(t)$:

$\displaystyle E[q(t)|\rho(t)=b]$
$\displaystyle=E[T\cdot\left(\frac{b}{X_{t}}-1\right)^{+}]=T\cdot\int_{0}^{b}\left(\frac{b}{a}-1\right)\cdot
f(a)\cdot da,$ (14) $\displaystyle E[U(t)|\rho(t)=b]$
$\displaystyle=E[\left(1-\frac{b}{X_{t}}\right)^{+}]=\int_{b}^{\infty}\left(1-\frac{b}{a}\right)\cdot
f(a)\cdot da.$

Notice that Eq. (14) is identical to the curve $g^{f}$ from Eq. (11), i.e.,
the point $(E[q(t)|\rho(t)=b],E[U(t)|\rho(t)=b])$ lies on the curve $g^{f}$.
Indeed, as we vary $b\in\mathbb{R}^{+}$, this point traces the entirety of
$g^{f}$.

Let the PDF of $\rho$ be $f_{r_{t}}$ in time step $t$. This distribution
depends on the congestion control strategy and can be different for different
time steps. We have:

$\displaystyle E[q(t)]$
$\displaystyle=E_{\rho(t)}[E[q(t)|\rho(t)]]=\int_{b=0}^{\infty}E[q(t)|\rho(t)=b]\cdot
f_{r_{t}}(b)\cdot db,$ (15) $\displaystyle E[U(t)]$
$\displaystyle=E_{\rho(t)}[E[U(t)|\rho(t)]]=\int_{b=0}^{\infty}E[U(t)|\rho=b]\cdot
f_{r_{t}}(b)\cdot db.$

Eq. (15) shows that the point $(E[q(t)],E[U(t)])$ is a weighted average of the
points $(E[q(t)|\rho(t)=b],E[U(t)|\rho(t)=b])$ for different values of $b$,
all of which lie on the curve $g^{f}$. The actual value of $(E[q(t)],E[U(t)])$
depends on the distribution $f_{r_{t}}$, which determines the weight given to
each point on $g^{f}$. But regardless of $f_{r_{t}}$, the point
$(E[q(t)],E[U(t)])$ will lie in the set $\mathbb{C}^{f}$ since $g^{f}$ is
convex.

Finally, let us consider the expected queuing delay and underutilization over
multiple time steps:

(16) $\displaystyle E[\bar{q}(t)]$
$\displaystyle=E\left[\frac{\sum_{i=1}^{t}q(i)}{t}\right]=\frac{\sum_{i=1}^{t}E[q(i)]}{t},$
$\displaystyle E[\bar{U}(t)]$
$\displaystyle=E\left[\frac{\sum_{i=1}^{t}U(i)}{t}\right]=\frac{\sum_{i=1}^{t}E[U(i)]}{t}.$

The point $(E[\bar{q}(t)],E[\bar{U}(t)])$ is the average of the points
$(E[q(i)],E[U(i)])$ for $1\leq i\leq t$. Since all these points belong to the
convex set $\mathbb{C}^{f}$, their average must also lie in the set
$\mathbb{C}^{f}$. This completes the proof. ∎

###  4.2. Is the Performance Bound Achievable?

The analysis in the previous section provides insight into how to achieve a
particular point on performance bound. The key observation is that we need to
maintain the same “load” $\rho(t)$ in every time step. Recall that $\rho(t)$
determines the operating point $(E[q(t)],E[U(t)])$ achieved on the curve
$g^{f}$ in each time step. If $\rho(t)$ changes from round to round, then over
multiple time steps we will end up at a sub-optimal point in the interior of
$\mathbb{C}^{f}$. However, if the congestion control algorithm can keep
$\rho(t)$ constant over time, it can achieve an optimal tradeoff between
underutilization and queuing delay.

Setting $\rho(t)=C$ (for some constant $C$) in Eq. (12) suggests the following
control law:

(17) $\displaystyle s(t)$
$\displaystyle=C\cdot\mu(t-1)-\frac{Q(t-1)}{T},\quad\forall t\in\mathbb{N}.$

The first term selects a sending rate proportional to the current link
capacity $\mu(t-1)$. This is an intuitive choice since the next capacity
$\mu(t)$ is also proportional to $\mu(t-1)$ (albeit with an unknown
multiplicative factor). The second term deducts a rate based on the current
queue backlog from the sending rate. This deduction corresponds to the rate
necessary to drain the current queue backlog within one time step. The
parameter $C$ controls the tradeoff between underutilization and queuing
delay. As $C$ increases, the congestion control sends more aggressively,
favoring high utilization at the expense of queuing delay. This corresponds to
moving to the right on the curve $g^{f}$ (see Fig. 5).

However, it may not always be possible to strictly follow the above rule. In
Eq. (17), $s(t)$ can become negative, but of course the sending rate must be
non-negative. For example, it might so happen by chance that the link capacity
drops rapidly over a number of consecutive time steps, leading to a large
queue build up. If in any time step $t$, $Q(t-1)$ exceeds $T\cdot
C\cdot\mu(t-1)$, then the sender will have to pick a negative sending rate to
follow $\rho(t)=C$, which is not possible.

This argument shows that depending on the distribution $f$ of the link
variation and the value $C$, it may not be possible to achieve some points on
the curve $g^{f}$. This is more likely for high values of $C$, which makes the
controller more aggressive, and for distributions $f$ where the link capacity
can drop significantly each time step. The following proposition gives
sufficient necessary conditions on $C$ such that the sender can always follow
the rule in Eq. (17) and enforce $\rho(t)=C$.

###### Proposition 0.

In the MIF model, it is possible to follow the strategy $\rho(t)=C$, $\forall
t\in\mathbb{N}$ iff

(18) $\displaystyle C$ $\displaystyle\leq\frac{X_{min}}{1-X_{min}},$

where $X_{min}$ is the minimum value of the random variable $X$
($P(X<X_{min})=0$).

###### Proof.

Please see Appendix D.2 ∎

This analysis shows us that the performance bound need not be tight. For any
$f(\cdot)$, the points $(x,g^{f}(x))$ where $E[q(t)|\rho(t)=C]=x$ but $C$ does
not meet the condition above might not be achievable.

###  4.3. Optimal Control Law

What happens when the above condition is not met and $Q(t-1)$ can exceed
$T\cdot C\cdot\mu(t-1)$? A natural question to ask is: in the event of
excessive queuing, should the sender just pick the minimum value for $\rho(t)$
such that $s(t)$ is non-negative? This corresponds to
$\rho(t)=\max(C,\frac{q(t-1)}{T})$, which implies a control law of the
following form:

(19) $\displaystyle s(t)$
$\displaystyle=\left(C\cdot\mu(t-1)-\frac{Q(t-1)}{T}\right)^{+},\quad\forall
t\in\mathbb{N}.$

We now show that the above rule can indeed achieve an optimal tradeoff between
underutilization and queuing delay. To this end, we formulate the congestion
control task as a Markov Decision Process (sutton2018reinforcement, ) (MDP)
and show that the above rule is an optimal policy for this MDP.

The MDP is defined as follows. The state at time step $t$ is given by
$(q(t-1),\mu(t-1))$. The congestion control “agent” observes this state and
selects an action — the sending rate $s_{t}\geq 0$. The state then transitions
to the next state $(q(t),\mu(t))$, and the agent incurs a weighted cost
$(w\cdot q(t)+U(t))$ for this time step, depending on the relative importance
of low queuing delay versus low underutilization. To see that this is an MDP,
recall that the transitions occur according to:

$\displaystyle\mu(t)$ $\displaystyle=\mu(t-1)\cdot X_{t}\quad\text{(per the
MIF model)},$ $\displaystyle q(t)$
$\displaystyle=T\cdot(\rho(t)/X_{t}-1)^{+}\quad\text{(per
Eq.~{}\eqref{eq:model1:proof_perfbound:qU_rt})},$

Therefore the next state is determined by the current state and the congestion
control action, since $\rho(t)=\frac{q(t-1)\mu(t-1)+T\cdot
s(t)}{T\cdot\mu(t-1)}$ (Eq. (12)).

The agent uses a control policy $\pi$ mapping the current state to a
probability distribution over possible actions (i.e., sending rates $s(t)\geq
0$). The policy can be deterministic or stochastic. The goal of the agent is
to minimize the following objective function over all policies:

(20) $\displaystyle J(\pi)=E\left[\sum_{t=1}^{\infty}\gamma^{t-1}\Big{(}w\cdot
q(t)+U(t)]\Big{)}\right].$

Here we use a standard discounted cost formulation, with discount factor
$\gamma\in(0,1)$.

###### Theorem 4.

In the MDP defined above, the optimal control policy that minimizes $J(\pi)$
takes the form:

(21) $\displaystyle
s(t)=\left(C(w,\gamma)\cdot\mu(t-1)-\frac{Q(t-1)}{T}\right)^{+},$

where $C(w,\gamma)$ is a constant.

###### Proof.

Define the optimal value function (sutton2018reinforcement, ) for our MDP as:

(22) $\displaystyle
V(q,\mu)=\min_{\pi}E\left[\sum_{t=1}^{\infty}\gamma^{t-1}\Big{(}w\cdot
q(t)+U(t)]\Big{)}\;\middle|\;q(0)=q,\mu(0)=\mu,s(t)\sim\pi(\cdot|q(t-1),\mu(t-1))\right].$

This is the minimum possible discounted expected sum of costs, starting from
initial state $(q,\mu)$ and following policy $\pi$, over all policies $\pi$.
333We only consider $f(\cdot)$ for which $V(q,\mu)$ exists.

The optimal value function satisfies the following Bellman Equation:

(23) $\displaystyle V(q,\mu)=\min_{s(1)\geq 0}E\left[w\cdot q(1)+U(1)+\gamma
V(q(1),\mu(1))\;\middle|\;q(0)=q,\mu(0)=\mu\right].$

The condition $s(1)\geq 0$ is equivalent to $\rho(1)\geq q/T$. Rewriting,

(24) $\displaystyle V(q,\mu)=\min_{\rho(1)\geq\frac{q}{T}}E\left[w\cdot
q(1)+U(1)+\gamma V(q(1),\mu(1))\;\middle|\;q(0)=q,\mu(0)=\mu\right].$

###### Lemma 0.

$V(q,\mu)$ is a convex function of $q$ and does not depend on $\mu$.

###### Proof.

See Appendix D.3. ∎

Since $V$ does not depend on $\mu$, henceforth we will write the optimal value
function as $V(q)$. To complete the proof, we exploit the fact that $q(t)$ and
$U(t)$ only depend on the value of $\rho(t)$ and define a helper function
$W(\cdot)$ as follows,

(25) $\displaystyle W(\rho)$ $\displaystyle=E\left[w\cdot
q(1)+U(1)+\gamma\cdot V(q(1))\;\middle|\;\rho(1)=\rho\right],$ $\displaystyle
V(q)$ $\displaystyle=\min_{\rho\geq\frac{q}{T}}(W(\rho)).$

$W(\rho)$ is the minimum expected cost when we restrict the first action to
$\rho(1)=\rho$ and then act optimally from that step onward.

###### Lemma 0.

$W(\rho)$ is a convex function in $\rho$.

###### Proof.

The proof directly follows from proof of Sub lemma 0.3 in Appendix D.3. ∎

Let the minimum value of $W(\cdot)$ occur at $\rho^{*}$. Then, the convexity
of $W(\cdot)$ combined with Eq. (25) establishes that the optimal control law
is of the form $\rho(t)=\max(\rho^{*},q(t-1)/T)$. To see this, note that the
minimizer of $W(\rho)$ in Eq. (25) is $\rho=q/T$ if $\rho^{*}<q/T$, and
$\rho=\rho^{*}$ otherwise. Furthermore, note that $\rho^{*}$ depends on
$\gamma$ and $w$. Defining $C(w,\gamma)=\rho^{*}$ and using Eq. (12) we get
the optimal control law from the Theorem.

∎

###  4.4. Extension: Incorporating Prediction for Link Capacity

It is natural to ask what if the sender could predict the link capacity with
some degree of accuracy? Like the MIF model, does there exist a fundamental
performance bound? How can the sender use the prediction and what is the
optimal control law? To answer these questions, we will now extend the MIF
model to include prediction. We refer to this new model as Prediction-based
Multiplicative I.I.D. Factors (PMIF) model. In this model, at the start of
every time step, the sender has access to a prediction of the link capacity
(e.g., based on past behavior or underlying link information such as signal
strength). We denote the link capacity prediction for time step $t$ by
$Pred(t-1)$ .

In the PMIF model, the predicted link capacity can deviate from the true link
capacity. We use random variable $X^{p}$ to represent how far is the
prediction relative to the true link capacity. In other words, the random
variable $X^{p}$ is a measure of uncertainty in the true link capacity given
the prediction. Formally, the uncertainty in the link capacity is governed by,

(26) $\mu(t)=Pred(t-1)\cdot X_{t}^{p},$

where $X_{i}^{p}$ is an I.I.D random variable with $f^{p}(\cdot)$ as its
probability density function (PDF) and $P(X_{i}^{p}<=0)=0$.

Note that, we do not attempt to come up with a predictor ourselves; rather, we
only analyse the impact of prediction error on the design of congestion
control for time-varying links.

####  4.4.1. Performance Bound

###### Corollary 0.

In the PMIF model, for any causal congestion control protocol, for any
$t\in\mathbb{N}$, the point ($E[\bar{q}(t)]$, $E[\bar{U}(t)]$) always lies in
a convex set $\mathbb{C}^{f^{p}}\triangleq\\{(x,y)|y>=g^{f^{p}}(x)\\}$, where
$g^{f^{p}}(\cdot)$ is defined by Eq. (11).

The performance bound is dependent on the characteristics of the random
variable $X^{p}$ and consequently the accuracy of prediction. The better the
prediction, the better the performance bound.

###### Proof.

To prove this corollary, we will use the techniques from the proof of Theorem
1. Using $\mu(t)=Pred(t-1)\cdot X^{p}_{t}$, we can rewrite $q(t)$ and $U(t)$
as follows,

$\displaystyle q(t)$
$\displaystyle=T\cdot\left(\frac{\frac{Q(t-1)}{T}+s(t)}{Pred(t-1)\cdot
X_{t}^{p}}-1\right)^{+},$ $\displaystyle
U(t)=\left(1-\frac{\frac{Q(t-1)}{T}+s(t)}{Pred(t-1)\cdot
X_{t}^{p}}\right)^{+}.$

Similar to $\rho(t)$ from Eq. (12), we define a new quantity $\rho^{p}(t)$ as
follows,

(28) $\displaystyle\rho^{p}(t)$
$\displaystyle=\frac{\frac{Q(t-1)}{T}+s(t)}{Pred(t-1)}.$

Intuitively, $\rho^{p}(t)$ can be thought of as the load on link in time step
$t$ relative to the prediction of the link capacity ($Pred(t-1)$). We can
rewrite $q(t)$ and $U(t)$ in terms of $\rho^{p}(t)$,

(29) $\displaystyle q(t)$
$\displaystyle=T\cdot\left(\frac{\rho^{p}(t)}{X_{t}^{p}}-1\right)^{+},$
$\displaystyle U(t)$
$\displaystyle=\left(1-\frac{\rho^{p}(t)}{X_{t}^{p}}\right)^{+}.$

Notice that the equation above is analogous to Eq. (13). Thus, we can apply
the same techniques as in the proof for Theorem 1 to show that the point
$(E[q(t)|\rho^{p}(t)=b],E[U(t)|\rho^{p}(t)=b])$ lies on the curve
$g^{f^{p}}(\cdot)$. Both the points $(E[q(t)],E[U(t)])$ and
$(E[\bar{q}(t)],E[\bar{U}(t)])$ lie in the convex set $\mathbb{C}^{f^{p}}$. ∎

####  4.4.2. Optimal Control Law

The analysis in the previous section shows us that we can achieve a particular
point $(x,g^{f^{p}}(x))$ on the performance bound by following a strategy of
the form,

(30) $\displaystyle\rho^{p}(t)$ $\displaystyle=C^{p},$ $\displaystyle s(t)$
$\displaystyle=C^{p}\cdot Pred(t-1)-\frac{Q(t-1)}{T},$ $\displaystyle\forall
t\in\mathbb{N},$

where $E[q(t)|\rho^{p}(t)=C^{p}]=x$. The key is keeping the link load relative
to the prediction of the link capacity the same in every time step, regardless
of the state of the system. However, similar to §4.2, following this strategy
might not be possible for all values of $C^{p}$. In the event of excessive
queuing ($Q(t-1)>T\cdot C^{p}\cdot Pred(t-1)$), for $\rho^{p}(t)=C^{p}$, the
sender needs to pick a negative value for $s(t)$ (from Eq. (28)) which is not
possible. Is simply following $s(t)=(C^{p}\cdot
Pred(t-1)-\frac{Q(t-1)}{T})^{+}$ optimal in just situations?

Similar to the MIF model, we can formulate the congestion control task as a
MDP and show that the above control law is optimal. The key change in the MDP
from the MIF model is that the state in time step $t$ is now given by
($q(t-1),\mu(t-1),Pred(t-1)$). The optimal control law for the MDP depends on
the dynamics of the predictions. Here, we only derive the exact optimal
control law for a simple model governing the evolution of $Pred$. In this MDP,
the evolution of $Pred$ is analogous to evolution of $\mu$ from the MIF model.
Formally,

(31) $\displaystyle Pred(t)=Pred(t-1)\cdot X^{pred}_{t},$

where $X_{i}^{pred}$ is an I.I.D random variable with $f^{pred}$ is its
probability density function (PDF) and $P(X_{i}^{pred}\leq 0)=0$. Other state
transitions are governed by,

$\displaystyle\mu(t)$ $\displaystyle=\mu(t-1)\cdot X^{p}_{t}\quad\text{(per
the PMIF model)},$ $\displaystyle q(t)$
$\displaystyle=T\cdot(\rho^{p}(t)/X^{p}_{t}-1)^{+}\quad\text{(per
Eq.~{}\eqref{eq:prediction_qU_rt})},$

The goal of the agent is to minimize the objective function ($J(\cdot)$ from
Eq. (20)) over all policies ($\pi$).

###### Corollary 0.

In the MDP defined above, the optimal control policy that minimizes $J(\pi)$
takes the form:

(32) $\displaystyle s(t)=\left(C^{p}(w,\gamma)\cdot
Pred(t-1)-\frac{Q(t-1)}{T}\right)^{+},$

where $C^{p}(w,\gamma)$ is a constant.

###### Proof.

Please see Appendix E.1 ∎

##  5\. Implications and Validation

In this section, we discuss some of the implications of the formal analysis
given above.

###  5.1. MIF Model

First, we validate our work against real cellular traces (Verizon LTE Uplink
and Downlink) taken from earlier work (mahimahi, ). Recall that the cellular
traces need not follow our model. For comparison, we also generate a synthetic
trace based on the MIF model with $X\sim e^{\textit{U(-1, 1})}$. For these
three traces, we plot the expected underutilization ($E[\bar{U}]$) versus the
expected normalized queuing delay ($E(\bar{q})$). We compare the performance
bound from Theorem 1 and the optimal control law from Theorem 4. We use the
empirical distribution of values $\frac{\mu(t)}{\mu(t-1)}$ from the traces as
our PDF $f$ to compute the performance bound and we simulate the optimal
control law for different values of $C(w,\gamma)$.

For the cellular traces, we also show the performance for various previously
proposed congestion control algorithms. We consider Cubic+Codel (cubic, ;
CoDel, ), XCP (xcp, ), ABC (abc, ; goyal2017rethinking, ), Sprout (sprout, ),
and Copa (copa, ) as representing the best performing alternatives. For the
existing algorithms, we use Mahimahi to emulate the traces (mahimahi, ).444The
dynamic range of the link capacity in the synthetic trace is not supported by
Mahimahi, and so we omit the comparison with prior work for that trace.For
Copa and Sprout, we use the authors’ UDP implementations. For the Cubic
endpoints, we use the Linux TCP implementation. For Codel, XCP, and ABC, we
use the implementation and configuration parameters from (abc, ). To make
these systems comparable to the derived bounds, we compute the queuing delay
once per baseline round trip.

Fig. 6 shows our main result: it is possible to achieve a smooth tradeoff
across a large range of underutilization and queuing delay. There is a
significant gap between the five existing congestion control algorithms and
the performance of the optimal control law on the Verizon traces. Note that
the formatting differs from Fig. 2 in that the x-axis is linear rather than
log scale. For the cellular traces, there is only a small gap between the
predicted performance bound and the optimal control law. This difference is
larger in the case of the synthetic trace. To achieve very low levels of
underutilization on the synthetic trace, the control law must be very
aggressive, sometimes resulting in large queues. As discussed in §4.2,
achieving the bound would require a negative sending rate to drain these
queues in one time step, which isn’t possible. For the cellular traces, this
rarely happens.

(a) Verizon Downlink

(b) Verizon Uplink

(c) Synthetic Trace

Figure 6. MIF model performance bound and performance curve for the optimal
control law.

Explicit versus implicit feedback: To compute the optimal sending rate, we
need the link capacity ($\mu(t-1)$) and queue size ($Q(t-1)$) in the previous
time step. Both these quantities are known at the link in time step $t-1$. The
link can communicate these quantities explicitly to the sender for computing
the optimal sending rate. However, explicit feedback is hard to deploy in many
scenarios and hasn’t seen much adoption in wireless networks (abc, ). Without
explicit feedback, the sender needs to infer the link capacity ($\mu(t-1)$)
indirectly. This inference is straightforward when there is no link
underutilization (the packet arrival rate at the receiver can serve as a
measure for the link capacity). However, when the link is underutilized, it
can be harder to infer the link capacity at either endpoint (abc, ). Because
implicit feedback introduces uncertainty in the link capacity ($\mu(t)$) at
the sender, the resulting performance may be sub-optimal. We see this effect
in Fig. 6. Explicit schemes like ABC and XCP which compute feedback based on
the link capacity outperform end-to-end schemes like Copa and Sprout that
infer the link capacity indirectly.

(a) Verizon Downlink

(b) Verizon Uplink

(c) Synthetic Trace

Figure 7. Comparison with XCP/RCP style control law — Each XCP curve shows
performance for a fixed value of $\alpha$ and variable value of $\beta$ (0 to
10).

Set sending rate based only on queue size and link capacity: Some explicit
congestion protocols, such as XCP and RCP (for a single sender), set the
sending rate according to the following rule555RCP uses a variant of the rule
in which it adjusts the rate in multiplicative (rather than additive)
increments.:

(33) $\displaystyle
s(t)=\left(s(t-1)+\alpha\cdot(\mu(t-1)-s(t-1))-\beta\cdot\frac{Q(t-1)}{T}\right)^{+},$

where $\alpha$ and $\beta$ are smoothing parameters (typically $<1$) that
govern stability, how quickly the protocol adapts to spare capacity
($\mu(t-1)-s(t-1))$, and how aggressively it drains the queue. Unlike our
optimal control law, the sending rate in these schemes is dependent on the
sending rate chosen in the previous time step. This does not attempt to keep
the relative link load $\rho(t)$ fixed in every time step. Instead, $\rho(t)$
is dependent on congestion control decisions in the previous time steps, and
any error in guessing the link rate is thus compounded.

Our analysis argues that the performance of such control laws might be sub-
optimal on links where the link capacity can vary widely over time. To
demonstrate this, we simulate an XCP/RCP style control law for various values
of $\alpha$ and $\beta$. Fig. 7 shows the result for the three traces. For
certain values of $\alpha$ and $\beta$, the performance gets close to the
optimal strategy curve. However, for most values the performance deviates from
the optimal, and in order to achieve the optimal, we need to tune both
$\alpha$ and $\beta$. For any fixed value of $\alpha$, varying $\beta$ is not
optimal across the entire range.

Do not change the queuing penalty term to adjust the performance trade-off:
Some explicit schemes, such as ABC, follow a different control law of the
form:

(34) $\displaystyle
s(t)=\left(\eta\cdot\mu(t-1)-\beta\frac{Q(t-1)}{T}\right)^{+},$

where $\eta$ is the target utilization and $\beta$ is a scaling factor for
queuing penalty.

This control law is similar to the optimal control law. However, in such
control laws the parameter $\eta$ (analogous to $C(w,\gamma)$ in the optimal
control law) is incorrectly viewed as the target utilization and is usually
set to a value just below one (abc, ). In order to adjust the trade-off
between utilization and queuing delay such schemes vary $\beta$. The optimal
control law argues that the sender should instead use a fixed value of
$\beta=1$ and vary the parameter $C(w,\gamma)$ (or $\eta$) instead; setting it
much less than or greater than one depending on the desired trade-off between
queueing delay and underutilization.

We simulate the ABC style control law for a fixed value of $\eta=1$ and
different values of $\beta$. Fig. 8 shows the result. As expected, the ABC
control law deviates from optimal performance, particularly for low values of
queueing delay.

(a) Verizon Downlink

(b) Verizon Uplink

(c) Synthetic Trace

Figure 8. Comparison with ABC style control law.

Implications for Link Layer Design: Our analysis also has implications for
link layer design (see Appendix C). For example, our analysis reveals that
variability and uncertainty in link capacity restricts achievable performance.
For cellular networks, designing schedulers with a smoother allocation for
link capacity can improve performance. Additionally, knowledge about the
achievable performance can enable cellular operators to provide guaranteed
service level agreements for latency-sensitive applications such as video
conferencing.

###  5.2. PMIF Model

To demonstrate that good prediction can improve performance substantially this
model, we use the traces from §5.1. At the start of each time step $t$, we
synthetically supply a prediction ($Pred(t-1)$) to the sender. To demonstrate
improvements over the optimal control law (without prediction) from the MIF
model, we intentionally pick a prediction with good accuracy ($X^{p}\sim
U(0.8,1.2)$) such that for each trace $g^{f^{p}}$ is better than $g^{f}$.
Using $X^{p}$ and $\mu(t)$, we sample the value for $Pred(t-1)$ with Eq. (26)
as follows:

(35) $\displaystyle Pred(t-1)=\frac{\mu(t)}{X^{p}}.$

Fig. 9 shows the performance bound ($g^{f^{p}}(\cdot)$) obtained in Corollary
7. The figure also shows the performance curve when following the optimal
control law from Corollary 8 for different values of $C^{p}(w,\gamma)$. We
also include the performance bound ($g^{f}(\cdot)$) and the performance curve
of the optimal control law based on the MIF model. Indeed, the optimal control
law with prediction outperforms that based on the MIF model. Additionally, the
optimal control law achieves performance close to the performance bound.

This result shows that that improving link rate prediction could provide large
performance gains. This could come from better modelling of the statistical
properties of wireless links, or from physical layer information such as
signal strength (predictwifi, ; pbe_cc, ; xie2015pistream, ).

(a) Verizon Downlink

(b) Verizon Uplink

(c) Synthetic Trace(MIF model)

Figure 9. Impact of incorporating prediction — Incorporating prediction can
substantially improve performance.

##  6\. A General Markovian Link Model

In the MIF model, tne link capacity varies independently from step to step and
the relative variation is the same for every time step. In a more realistic
setting, the variability may instead depend on the _state of the link_. For
example, cellular links have a maximum rate, and the likelihood of relative
increase in capacity is likely to be higher at lower link rates compared to
higher link rates. In this section, we extend the MIF model to allow for a
more expressive Markovian process governing the link capacity. We refer to
this extension as the State-dependent Multiplicative Factors (SMF) model.

Let $S(t)\in\textbf{S}$ represent the state of the link in time step $t$,
where S denotes the set of all possible link states. The link state includes
the link capacity $\mu(t)$ and any other quantity that can impact how the link
capacity varies in the next time step. For example, in cellular networks where
multiple users compete at a base station, the number of users at the base
station might be part of the link state. To capture variations in the link
state, we model the link state itself as a Markov chain. The link state in
time step $t-1$ ($S(t-1)$) governs the probability distribution of the link
state in time step $t$ ($S(t)$). $S(t-1)$ implicitly also governs the
probability distribution of link capacity in the next time step ($\mu(t)$).

The number of distinct states in the set S can be infinite. For ease of
presentation, we will assume that the number of such states is finite, but our
analysis holds for continuous state spaces as well. Note that the above model
includes as a special case any Markovian link rate process governed by a
probability transition function $P(\mu(t+1)|\mu(t))$; the link state is simply
$S(t)=\mu(t)$ in this case.

Let $\mathbb{A}$ be the probability transition matrix for the link state. This
matrix defines the probability $P^{A}(S(t)=k_{1}|S(t-1)=k_{2})$. For ease of
analysis, we first convert this model to a form analogous to Eq. (10). The
Markov chain for the link state can be described in an alternate form as
follows. Let $S(t)$ conditioned on the event $\\{S(t-1)=k\\}$ have
distribution $H^{k}$. We can write: $S(t)=Z_{t}^{k}$ if $S(t-1)=k$, where
$Z_{t}^{k}$ is an I.I.D random variable with distribution $H^{k}$ ($\forall
k\in\textbf{S},\forall t\in\mathbb{N}$). In short:

(36) $\displaystyle S(t)=Z_{t}^{S(t-1)}.$

Since $\mu(t)$ is determined by $S(t)$, we can similarly write $\mu(t)$ as
follows,

(37) $\displaystyle\mu(t)$ $\displaystyle=Y_{t}^{S(t-1)},$

where $\forall k\in\textbf{S},\forall t\in\mathbb{N}$, $Y_{t}^{k}$ is an I.I.D
random variable. Similarly, since $\mu(t-1)$ is given by $S(t-1)$, we can
rewrite the above equation as follows,

(38) $\displaystyle\mu(t)$ $\displaystyle=\mu(t-1)\cdot X_{t}^{S(t-1)},$

where $\forall k\in\textbf{S},X_{t}^{k}$ is an I.I.D random variable.

Let $f^{k}(\cdot)$ be the PDF associated with random variable $X^{k}$. $f^{k}$
can be calculated from the transition matrix $\mathbb{A}$. The equation above
(governing the uncertainty in the link capacity at the sender) is now
analogous to Eq. (10). We make the following assumptions:

Assumptions: (1) Link state transitions are independent of the decisions of
the congestion control protocol, i.e., the sending rate and queuing delay do
not affect how the link state changes. (2) Link state has a stationary
distribution in the steady state given by the function $\lambda(\cdot)$, i.e.
$P(S(t)=k)\to\lambda(k)$, and $t\to\infty$. (3) The sender has access to the
link state information in the previous time step ($S(t-1)$) for deciding the
sending rate in time step $t$. (4) The starting state ($S(0)$) has the same
distribution as the stationary distribution $\lambda$. This implies,
$P(S(t)=k)=\lambda(k),\forall t\in\mathbb{N}$.666This assumption is merely for
convenience of analysis. In the more general case of starting from any
arbitrary initial state, the performance bound we provide will hold after a
sufficient “mixing” time has passed so that the link state distribution is
close the stationary distribution. The optimal control law we derive holds
regardless of the initial state. 5) The link capacity is always positive,
i.e., we only consider $\mathbb{A}$ such that $P(\mu(t)<=0)=0,\forall
t\in\mathbb{N}$.

Similar to our analysis for the MIF model, we derive a performance bound
between $E[\bar{q}(t)]$ and $E[\bar{U}(t)]$ (§6.1), use it to draw insights
about how the optimal congestion controller (§6.2), and derive the optimal
control law by posing the task as a MDP (§6.3). Finally, we discuss the
implications of our analysis and validate our findings (§6.4).

###  6.1. Performance Bound

###### Theorem 1.

In the SMF model, for any causal congestion control protocol, for any $t\in
N$,the point $(E[\bar{q}(t)],E[\bar{U}(t)])$ lies in a convex set
$\mathbb{D}^{A}$. The point $(x,y)\in\mathbb{D}^{A}$ iff

(39) $\displaystyle x$ $\displaystyle=\sum_{k\in\textbf{S}}\lambda(k)\cdot
x^{k},$ $\displaystyle y=\sum_{k\in\textbf{S}}\lambda(k)\cdot y^{k},$

where $\forall k\in\textbf{S}$, the point
$(x^{k},y^{k})\in\mathbb{C}^{f^{k}}$. The set $\mathbb{C}^{f^{k}}$ is as
defined in Theorem 1 with $f^{k}(\cdot)$ as the PDF

The performance bound is dependent on the probability distribution of the link
state ($\lambda$) and how each link state $S(t-1)$ impacts the relative
variability in link capacity in the next time step ($f^{S(t-1)}$). The set
$\mathbb{D}^{A}$ is a weighted average of the sets
$\cup_{k\in\textbf{S}}\\{\mathbb{C}^{f^{k}}\\}$. $\mathbb{C}^{f^{k}}$ in
itself is the performance bound when the relative variability in link capacity
is the same in each time step according to link state $k$ (i.e.,
$\mu(t)=\mu(t-1)\cdot X^{k}_{t},\forall t\in\mathbb{N}$).

###### Proof.

Since link state ($S(t-1)$) governs the link capacity in the next time step
($\mu(t)$), the queuing delay and underutilization in time step $t$ also
depend on $S(t-1)$. We can calculate $E[q(t)]$ and $E[U(t)]$ using the
conditional expected values $E[q(t)|S(t-1)=k]$ and $E[U(t)|S(t-1)=k]$ as
follows

$\displaystyle E[q(t)]$
$\displaystyle=E_{S(t-1)}[E[q(t)|S(t-1)=k]]=\sum_{k\in\textbf{S}}\lambda(k)\cdot
E[q(t)|S(t-1)=k],$ (40) $\displaystyle E[U(t)]$
$\displaystyle=E_{S(t-1)}[E[U(t)|S(t-1)=k]]=\sum_{k\in\textbf{S}}\lambda(k)\cdot
E[U(t)|S(t-1)=k].$

To prove our theorem, we will prove the following lemma about the conditional
expected values of queuing delay and underutilization,

###### Lemma 0.

$\forall k\in\textbf{S}$, the point
$(E[q(t)|S(t-1)=k],E[U(t)|S(t-1)=k])\in\mathbb{C}^{f^{k}}$.

###### Proof.

The conditional queuing delay $(q(t)|(S(t-1)=k))$ and underutilization
$(U(t)|S(t-1)=k)$ can be calculated as follows,

$\displaystyle q(t)|(S(t-1)=k)$
$\displaystyle=T\cdot\left(\frac{\frac{Q(t-1)}{T}+s(t)}{\mu(t-1)\cdot
X_{t}^{k}}-1\right)^{+}=T\cdot\left(\frac{\rho(t)}{X_{t}^{k}}-1\right)^{+},$
(41) $\displaystyle U(t)|(S(t-1)=k)$
$\displaystyle=\left(1-\frac{\frac{Q(t-1)}{T}+s(t)}{\mu(t-1)\cdot
X_{t}^{k}}\right)^{+}=\left(1-\frac{\rho(t)}{X_{t}^{k}}\right)^{+},$

where $\rho(t)$ is as defined by Eq. (12).

Given the link state in the previous time step ($S(t-1)$), the relative link
load ($\rho(t)$) solely governs the probability distribution of $q(t)$ and
$U(t)$. The equation above is in fact analogous to Eq. (13) from the MIF
model. Thus, we can apply the same techniques as in the proof of Theorem 1.
The point $(E[q(t)|S(t-1)=k,\rho(t)=b],E[U(t)|S(t-1)=k,\rho(t)=b])$ lies on
the curve $g^{f^{k}}(\cdot)$. Consequently the point
$(E[q(t)|S(t-1)=k],E[U(t)|S(t-1)=k])$ lies in the convex set
$\mathbb{C}^{f^{k}}$.∎

The Lemma along with Eq. (40) establishes that the point
$(E[q(t)],E[U(t)])\in\mathbb{D}^{A}$. The point
$(E[\bar{q}(t)],E[\bar{U}(t)])$ also belongs to $\mathbb{D}^{A}$ (using the
same technique as the multi-time step proof of Theorem 1). Since
$\mathbb{C}^{f^{k}}$ is convex $\forall k\in\textbf{S}$, the weighted average
of $\cup_{k\in\textbf{S}}\\{\mathbb{C}^{f^{k}}\\}$ is convex, and
$\mathbb{D}^{A}$ is convex. ∎

Next, we will show a simple method for computing the set $\mathbb{D}^{A}$.
This method will provide us insights into the potential form of the optimal
control law.

####  6.1.1. How to compute the set $\mathbb{D}^{A}$?

To compute $\mathbb{D}^{A}$, we will calculate it’s boundary function
$g^{A}(\cdot)$. Point $(x,y)$ belongs to $\mathbb{D}^{A}$ iff $y\geq
g^{A}(x)$. The boundary point $(x,g^{A}(x))$ must be a weighted average of
points on the curves $\cup_{k\in\textbf{S}}\\{g^{f^{k}}(\cdot)\\}$. Formally,

(42) $\displaystyle x$ $\displaystyle=\sum_{k\in\textbf{S}}\lambda(k)\cdot
x^{k},$ $\displaystyle y=\sum_{k\in\textbf{S}}\lambda(k)\cdot
g^{f^{k}}(x^{k}).$

This is because for a given $x^{k}$, the min value of $y^{k}$, such that
$(x^{k},y^{k})\in\mathbb{C}^{f^{k}}$ occurs at $y^{k}=g^{f^{k}}(x^{k})$.

###### Proposition 0.

The point $(x,y)\in\mathbb{D}^{A}$, given by

$\displaystyle x$ $\displaystyle=\sum_{k\in\textbf{S}}\lambda(k)\cdot x^{k},$
$\displaystyle y=\sum_{k\in\textbf{S}}\lambda(k)\cdot g^{f^{k}}(x^{k}),$

is on the boundary ($y=g^{A}(x)$) iff,

(44) $\displaystyle
g^{f^{i}}{{}^{\prime}}(x^{i})=g^{f^{j}}{{}^{\prime}}(x^{j})$
$\displaystyle,\forall i,j\in\textbf{S}.$

###### Proof.

Please see Appendix F.1 for proof details. ∎

This proposition states that the point $(x,g^{A}(x))$ is a weighted average of
points $\cup_{k\in\textbf{S}}\\{(x^{k},g^{f^{k}}(x^{k}))\\}$ with the same
slope. In other words, we are averaging points such that the marginal trade-
off between expected queuing delay and underutilization is same on the curves
$\cup_{k\in\textbf{S}}\\{g^{f^{k}}(\cdot)\\}$.

###  6.2. Is the Performance Bound Achievable?

Recall, the point $(E[q(t)|S(t-1)=k,\rho(t)=b],E[U(t)|S(t-1)=k,\rho(t)=b])$
lies on the curve $g^{f^{k}}(\cdot)$. The proposition in the previous
subsection establishes that we can achieve a particular point ($x,g^{A}(x)$)
on the performance bound where $x=\sum_{k\in\textbf{S}}(\lambda(k)\cdot
x^{k})$ and $g^{f^{k}}{{}^{\prime}}(x^{k})=g^{A}{{}^{\prime}}(x),\forall
k\in\textbf{S}$ by following a strategy of the form,

(45) $\displaystyle\rho(t)|(S(t-1)=k)$ $\displaystyle=C^{A}(k)\Longrightarrow
s(t)|(S(t-1)=k)=C^{A}(k)\cdot\mu(t-1)-\frac{Q(t-1)}{T},$ $\displaystyle\forall
k\in\textbf{S},$

where $\forall k\in\textbf{S},C^{A}(k)$ satisfies
$x^{k}=E[q(t)|S(t-1)=k,\rho(t)=C^{A}(k)])$.

In simple terms, the above control law is arguing for setting the relative
link load based solely on the link state in the previous time step.
Intuitively this is as expected because the probability distribution of $q(t)$
and $U(t)$ is only dependent on $\rho(t)$ and $S(t-1)$ (Eq. (41)). Again,
following this strategy might not always be possible. In particular, in the
event of excessive queuing ($Q(t-1)>T\cdot C^{A}(S(t-1))\cdot\mu(t-1)$), for
$\rho(t)=C^{A}(S(t-1)$, the sender needs to pick a negative value for $s(t)$
(from Eq. (12)) which is not possible.

We will now establish the necessary conditions under which the sender can
follow the strategy $\rho(t)=C^{A}(S(t-1))$ exactly.

###### Proposition 0.

In the SMF model , it is possible to follow the strategy
$\rho(t)=C^{A}(S(t-1))$ $\forall t\in\mathbb{N}$ iff

(46) $\displaystyle\frac{C^{A}(k_{1})}{X_{min}^{k_{1}}}-1$ $\displaystyle\leq
C^{A}(k_{2}),$ $\displaystyle\forall k_{1},k_{2}\in\textbf{S},$

where $\forall k\in\textbf{S},X^{k}_{min}$ is the minimum value of the random
variable $X^{k}$ ($P(X^{k}<X^{k}_{min})=0$).

###### Proof.

Please see Appendix F.2 for the proof. ∎

This condition restricts excessive queue build up for all possible transitions
in the link state $S(t-1)=k_{1}$ to $S(t)=k_{2}$. Again, the performance bound
need not be tight.

###  6.3. Optimal Control Law

What happens when the above condition is not met? What is the optimal control
law? Will the following variant of the strategy in Proposition 4 –
$s(t)|(S(t-1)=k)=\left(C^{A}(k)\cdot\mu(t-1)-\frac{Q(t-1)}{T}\right)^{+}$,
where $C^{A}(k)$ is as defined in Eq. (45) – be optimal?

To answer this question, as before, we formulate an MDP. The MDP is similar to
that in the MIF model but the state at time step $t$ is given by
$(q(t-1),\mu(t-1),S(t-1))$. The state transitions occur according to:

$\displaystyle\mu(t)$ $\displaystyle=\mu(t-1)\cdot
X^{S(t-1)}_{t}\quad\text{(per the SMF model)},$ $\displaystyle S(t)$
$\displaystyle=Z^{S(t-1)}_{t}\quad\text{(per the SMF model)},$ $\displaystyle
q(t)$ $\displaystyle=T\cdot(\rho(t)/X^{S(t-1)}_{t}-1)^{+}\quad\text{(per
Eq.~{}\eqref{eq:model3:proof_perfbound:generic_markov_system})}.$

The goal of the agent is to minimize the objective function ($J(\cdot)$ from
Eq. (20)) over all policies ($\pi$):

###### Corollary 0.

In the MDP defined above, the optimal control policy that minimizes $J(\pi)$
takes the form:

(47) $\displaystyle
s(t)=\left(C^{A}(w,\gamma,S(t-1))\cdot\mu(t-1)-\frac{Q(t-1)}{T}\right)^{+},$

where $\forall k\in\textbf{S},C^{A}(w,\gamma,k)$ is a constant.

###### Proof.

Please see Appendix F.3 ∎

###  6.4. Implications and Validation

We use the traces from §5.1 to demonstrate the performance of the optimal
control law based on the SMF model. Since we only have access to link capacity
information in the traces, we treat link capacity as the link state
($S(t)=\mu(t)$). In other words, the relative variation in link capacity in a
time step in itself is dependent on the link capacity in the previous time
step. Similar to §5.1 we use the link capacity from traces to generate the
PDFs $\cup_{k\in\textbf{S}}\\{f^{k}(\cdot)\\}$. Fig. 10 shows the performance
bound ($g^{A}(\cdot)$) and the performance curve for the optimal control
law777 For different values of $w$, we approximate the value of
$C^{A}(w,\gamma,k)$ using the curve $g^{A}(\cdot)$ (Eq. (45)). In particular,
in the MDP formulation, $\gamma\to 0$ (or $J(\pi)=E[w\cdot q(1)+U(1)]$)
corresponds to minimizing the cost in a single time step. Therefore, assuming
$\gamma\to 0$, we can use the curve $g^{A}$ to compute $C^{A}(w,\gamma,k)$,
formally,
$g^{f^{k}}{{}^{\prime}}([E[q(t)|S(t-1)=k,\rho(t)=C^{A}(w,\gamma,k)])=-w,\forall
k\in\textbf{S}$. . As expected, on cellular traces, both the performance bound
and the performance curve for the optimal control law based on the SMF model
outperform those based on the MIF model. Compared to the MIF model, the SMF
model provides more degrees of freedom to model the variations in link
capacity. For example, unlike the MIF model, when the link capacity is low it
is more likely to increase than if the link capacity is high. With access to
the physical layer information, we might be able to use the SMF model to
better capture the nuances of variations in the link capacity and improve
performance even further. Note also that since the relative variation in link
capacity for the synthetic trace (generated using the MIF model in §5.1) is
same in every time step, there is no improvement from using the SMF optimal
control law over the MIF model on those traces.

(a) Verizon Downlink

(b) Verizon Uplink

(c) Synthetic trace (MIF model)

Figure 10. Performance bound and performance curve for the optimal control law
based on the SMF model.

##  7\. Discussion

Continuous-time Domain. In our analysis – for our models and system equations
– we used the discrete-time domain. However, obviously wireless links operate
in the continuous-time domain. Thus, we might miss sub-RTT effects. We leave
extending our analysis to the continuous-time domain as future work. Such an
analysis is likely to be substantially more complex than the one we presented
here. That said, are the optimal control laws from our analysis _stable_ in
the continuous-time domain? We show that these control laws are indeed
globally asymptotically stable. In particular, we show that if the link
capacity stops changing after a time instant $t_{0}$, regardless of the
initial conditions, the sending rate and the queuing delay at the link will
converge to certain values $s^{*}$ and $q^{*}$ that depend on the control law
parameters. Please see Appendix G for details.

Implications for Learning-based Congestion Control. Our analysis reveals the
optimal form of the control law for various link models. If the link rate
generation process is known, one can derive the exact parameter values in the
control law by solving the Bellman equations of the corresponding MDPs. In
practice, the transition probabilities for the link capacity are typically not
known apriori and they may change over time. In such cases, we envision an
online learning system that continuously adjusts the control law in accordance
with the performance objective. We believe that compared to existing learning-
based approaches for congestion control (jay2019deep, ; li2018qtcp, ;
yan2018pantheon, ), knowledge about the form of the optimal control law can
reduce reduce sample complexity and enable faster adaptation.

##  8\. Conclusion

In this paper, we present a theoretical framework for analysing congestion
control behaviour on time-varying links. For tractability, we model the link
capacity using three simple yet general discrete-time Markov Chains that
capture the key components of variability in the capacity. For these models,
we show that there is a fundamental bound on the possible performance for
_any_ causal congestion control protocol. This bound is a consequence of the
fact that because of feedback delay, the sender does not know the current link
capacity, and it must guess to make congestion control decisions. Finally, we
derive the optimal control law for each model by posing the congestion control
task as a Markov Decision Process. The optimal control law differs from that
used by existing protocols and depends on the characteristics of variability
in the link capacity. We demonstrate the performance improvement of our
optimal control laws over existing protocols using real-world cellular traces.

## References

  * [1] V. Arun, M. T. Arashloo, A. Saeed, M. Alizadeh, and H. Balakrishnan.  Toward formally verifying congestion control behavior.  In Proceedings of the 2021 ACM SIGCOMM 2021 Conference, pages 1–16, 2021.
  * [2] V. Arun and H. Balakrishnan.  Copa: Practical delay-based congestion control for the internet.  In S. Banerjee and S. Seshan, editors, 15th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2018, Renton, WA, USA, April 9-11, 2018, pages 329–342. USENIX Association, 2018.
  * [3] N. Cardwell, Y. Cheng, C. S. Gunn, S. H. Yeganeh, and V. Jacobson.  BBR: Congestion-Based Congestion Control.  ACM Queue, 14(5):50:20–50:53, Oct. 2016.
  * [4] F. Cecchi and P. Jacko.  Scheduling of users with markovian time-varying transmission rates.  In Proceedings of the ACM SIGMETRICS/International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS ’13, page 129–140, New York, NY, USA, 2013. Association for Computing Machinery.
  * [5] D.-M. Chiu and R. Jain.  Analysis of the increase and decrease algorithms for congestion avoidance in computer networks.  Computer Networks and ISDN systems, 17(1):1–14, 1989.
  * [6] M. Dong, Q. Li, D. Zarchy, P. B. Godfrey, and M. Schapira.  PCC: re-architecting congestion control for consistent high performance.  In 12th USENIX Symposium on Networked Systems Design and Implementation, NSDI 15, Oakland, CA, USA, May 4-6, 2015, pages 395–408. USENIX Association, 2015.
  * [7] S. Floyd and V. Jacobson.  Random Early Detection Gateways for Congestion Avoidance.  IEEE/ACM Trans. on Networking, 1(4):397–413, 1993.
  * [8] P. Goyal, A. Agarwal, R. Netravali, M. Alizadeh, and H. Balakrishnan.  ABC: A simple explicit congestion controller for wireless networks.  In R. Bhagwan and G. Porter, editors, 17th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2020, Santa Clara, CA, USA, February 25-27, 2020, pages 353–372. USENIX Association, 2020.
  * [9] P. Goyal, M. Alizadeh, and H. Balakrishnan.  Rethinking congestion control for cellular networks.  In Proceedings of the 16th ACM Workshop on Hot Topics in Networks, pages 29–35, 2017.
  * [10] P. Goyal, P. Shah, K. Zhao, G. Nikolaidis, M. Alizadeh, and T. E. Anderson.  Backpressure flow control.  In 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2022).
  * [11] S. Ha, I. Rhee, and L. Xu.  CUBIC: A New TCP-Friendly High-Speed TCP Variant.  ACM SIGOPS Operating System Review, 42(5):64–74, July 2008.
  * [12] D. Halperin, W. Hu, A. Sheth, and D. Wetherall.  Predictable 802.11 packet delivery from wireless channel measurements.  In S. Kalyanaraman, V. N. Padmanabhan, K. K. Ramakrishnan, R. Shorey, and G. M. Voelker, editors, Proceedings of the ACM SIGCOMM 2010 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, New Delhi, India, August 30 -September 3, 2010, pages 159–170. ACM, 2010.
  * [13] M. Hock, R. Bless, and M. Zitterbart.  Experimental evaluation of bbr congestion control.  In 2017 IEEE 25th International Conference on Network Protocols (ICNP), pages 1–10. IEEE, 2017.
  * [14] J. C. Hoe.  Improving the Start-up Behavior of a Congestion Control Scheme for TCP.  In SIGCOMM, 1996.
  * [15] R. A. Howard.  Dynamic programming and markov processes.  1960\.
  * [16] V. Jacobson.  Congestion Avoidance and Control.  In SIGCOMM, 1988.
  * [17] R. Jain.  Congestion control and traffic management in atm networks: Recent advances and a survey.  Computer Networks and ISDN systems, 28(13):1723–1738, 1996.
  * [18] N. Jay, N. Rotman, B. Godfrey, M. Schapira, and A. Tamar.  A deep reinforcement learning perspective on internet congestion control.  In International Conference on Machine Learning, pages 3050–3059. PMLR, 2019.
  * [19] D. Katabi, M. Handley, and C. Rohrs.  Congestion Control for High Bandwidth-Delay Product Networks.  In SIGCOMM, 2002.
  * [20] L. Kleinrock.  Queueing systems, volume 2: Computer applications, volume 66.  wiley New York, 1976.
  * [21] G. Kumar, N. Dukkipati, K. Jang, H. M. G. Wassel, X. Wu, B. Montazeri, Y. Wang, K. Springborn, C. Alfeld, M. Ryan, D. Wetherall, and A. Vahdat.  Swift: Delay is simple and effective for congestion control in the datacenter.  In Proceedings of the Annual Conference of the ACM Special Interest Group on Data Communication on the Applications, Technologies, Architectures, and Protocols for Computer Communication, SIGCOMM ’20, page 514–528, New York, NY, USA, 2020. Association for Computing Machinery.
  * [22] W. Li, F. Zhou, K. R. Chowdhury, and W. Meleis.  Qtcp: Adaptive congestion control with reinforcement learning.  IEEE Transactions on Network Science and Engineering, 6(3):445–458, 2018.
  * [23] Y. Li, R. Miao, H. H. Liu, Y. Zhuang, F. Feng, L. Tang, Z. Cao, M. Zhang, F. Kelly, M. Alizadeh, et al.  HPCC: high precision congestion control.  In Proceedings of the ACM Special Interest Group on Data Communication, pages 44–58. ACM, 2019.
  * [24] F. Lu, H. Du, A. Jain, G. M. Voelker, A. C. Snoeren, and A. Terzis.  Cqic: Revisiting cross-layer congestion control for cellular networks.  In Proceedings of the 16th International Workshop on Mobile Computing Systems and Applications, pages 45–50. ACM, 2015.
  * [25] W. Massey.  The analysis of queues with time-varying rates for telecommunications models.  Telecommunication Systems, 21(2-4):173–204, 2002.
  * [26] M. Mathis, J. Semke, J. Mahdavi, and T. Ott.  The macroscopic behavior of the tcp congestion avoidance algorithm.  ACM SIGCOMM Computer Communication Review, 27(3):67–82, 1997.
  * [27] B. Montazeri, Y. Li, M. Alizadeh, and J. Ousterhout.  Homa: A receiver-driven low-latency transport protocol using network priorities.  In Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, pages 221–235. ACM, 2018.
  * [28] R. Netravali, A. Sivaraman, S. Das, A. Goyal, K. Winstein, J. Mickens, and H. Balakrishnan.  Mahimahi: Accurate Record-and-Replay for HTTP.  In USENIX Annual Technical Conference, 2015.
  * [29] K. Nichols and V. Jacobson.  Controlling Queue Delay.  ACM Queue, 10(5), May 2012.
  * [30] R. Pan, P. Natarajan, C. Piglione, M. Prabhu, V. Subramanian, F. Baker, and B. VerSteeg.  PIE: A lightweight control scheme to address the bufferbloat problem.  In Intl. Conf. on High Performance Switching and Routing (HPSR), 2013.
  * [31] W. Sun, L. Xu, S. Elbaum, and D. Zhao.  Model-Agnostic and efficient exploration of numerical state space of Real-World TCP congestion control implementations.  In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19), pages 719–734, Boston, MA, Feb. 2019. USENIX Association.
  * [32] R. S. Sutton and A. G. Barto.  Reinforcement learning: An introduction.  MIT press, 2018.
  * [33] C. Tai, J. Zhu, and N. Dukkipati.  Making Large Scale Deployment of RCP Practical for Real Networks.  In INFOCOM, 2008.
  * [34] W. Whitt.  Time-varying queues.  Queueing Models and Service Management, 1(2):079–164, 2018.
  * [35] K. Winstein, A. Sivaraman, and H. Balakrishnan.  Stochastic Forecasts Achieve High Throughput and Low Delay over Cellular Networks.  In NSDI, 2013.
  * [36] X. Xie, X. Zhang, S. Kumar, and L. E. Li.  pistream: Physical layer informed adaptive video streaming over lte.  In Proceedings of the 21st Annual International Conference on Mobile Computing and Networking, pages 413–425. ACM, 2015.
  * [37] Y. Xie, F. Yi, and K. Jamieson.  Pbe-cc: Congestion control via endpoint-centric, physical-layer bandwidth measurements.  In Proceedings of the Annual conference of the ACM Special Interest Group on Data Communication on the applications, technologies, architectures, and protocols for computer communication, pages 451–464, 2020\.
  * [38] F. Y. Yan, J. Ma, G. D. Hill, D. Raghavan, R. S. Wahby, P. A. Levis, and K. Winstein.  Pantheon: the training ground for internet congestion-control research.  In H. S. Gunawi and B. Reed, editors, 2018 USENIX Annual Technical Conference, USENIX ATC 2018, Boston, MA, USA, July 11-13, 2018, pages 731–743. USENIX Association, 2018.
  * [39] J. A. Yorke.  Asymptotic stability for one dimensional differential-delay equations.  Journal of Differential equations, 7(1):189–202, 1970.
  * [40] Y. Zaki, T. Pötsch, J. Chen, L. Subramanian, and C. Görg.  Adaptive congestion control for unpredictable cellular networks.  In ACM SIGCOMM Computer Communication Review, volume 45, pages 509–522. ACM, 2015.

##  Appendix A Analysis for Unused Link Capacity

We presented our analysis with queuing delay and underutilization as our
performance metrics. Our analysis can also be extended to other performance
metrics. For example, we can derive the optimal control law when we use unused
link capacity as the performance metrics instead of link underutilization.
Unused link capacity in time step $t$ ($L(t)$) can be given by,

(48) $\displaystyle L(t)$ $\displaystyle\triangleq\frac{(\mu(t)\cdot
T-s(t)\cdot T-Q(t-1))}{T}^{+}.$

Assuming the MIF model for variations in link capacity (i.e., the relative
variation in link capacity is same in every time step), we can write an
equation analogous to Eq. (14) for conditional expected value of $L(t)$ as
follows,

(49) $\displaystyle E[L(t)|r(t)=b]$
$\displaystyle=\mu(t-1)\cdot\int_{b}^{\infty}\left(a-b\right)\cdot f(a)\cdot
da.$

Notice that unlike underutilization, the conditional expected value of unused
link capacity in time step $t$ depends on the link capacity in the previous
time step ($\mu(t-1)$). Thus, we need to use the analysis from the SMF model
to calculate a performance bound and the optimal control law with
$E[\bar{L(t)}]$ and $E[\bar{q(t)}]$ as the performance metrics. In particular,
we treat link capacity as the link state ($S(t-1)=\mu(t-1)$). The optimal
control law is of the following form in this case,

(50) $\displaystyle
s(t)=\left(C^{\mu(t-1)}(w)\cdot\mu(t-1)-\frac{Q(t-1)}{T}\right)^{+}.$

Fig. 11 compares the performance curves for the optimal control law based on
link underutilization and unused link capacity. We find that the control law
based on $L(t)$ outperforms the one based on $U(t)$. In particular, we find
that the optimal control law based on $L(t)$ uses a lower value of
$C^{\mu(t-1)}(w)$ when $\mu(t-1)$ is lower. This is expected, as when
$\mu(t-1)$ is low, varying $r(t)$ has a relatively lower impact on lost
throughput compared to queuing delay.

(a) Verizon Downlink

(b) Verizon Uplink

Figure 11. Performance curve of the optimal control law based on unused link
capacity ($L(t)$).

##  Appendix B Analysis for Datacenter Networks

Datacenter networks have fixed capacity wired links that do not exhibit
variations in the link capacity. However, datacenter networks are still highly
variable: majority of the traffic is contributed by short flows that last only
a few RTTs. There is significant churn in the number of competing flows at a
link [10]. The optimal sending rate for a particular flow is a function of the
number of competing flows at the bottleneck at the current time ($N(t)$).
Because of the feedback delay, there is an uncertainty in the value of $N(t)$
at a sender at time $t$. We can potentially analyse such networks – where the
cause of variability is the churn in traffic – by modeling $N(t)$ as a markov
chain.We leave extending our analysis to such network environments as future
work.

##  Appendix C Implications for Link Layer Design

Our analysis establishes that there is a fundamental performance bound which
depends on the variability in the link capacity. The more variable the link is
the worse the achievable performance. To our knowledge, wireless link layer
protocols largely ignore this principle. For example, when arbitrating access
to shared media, scheduling algorithms that provide a relatively smoother link
capacity might be more desirable for latency-sensitive applications.
Additionally, cellular network operators may be able to offer more accurate
service level agreements (SLAs) to users based on our performance bounds.

Impact of reducing $T$: With 5G, cellular operators are trying to reduce non-
congestion related delay incurred in the radio access network. Content
providers are also striving to move their servers closer to the receiver and
reduce delays. One would expect that any reductions in the base RTT will
reduce the end-to-end delay linearly. Indeed, our analysis for the performance
bound also suggests that for a fixed value of underutilization, queuing delay
is linear in $T$ assuming that the characteristics of link variability does
not change with $T$. However, this assumption need not hold. Fig. 12 shows the
performance curve for the optimal control law from the MIF model on a Verizon
LTE trace for different values of $T$. We see that the gains in performance
are not linear and reducing $T$ has diminishing returns. This is because, when
we apply MIF model to this trace, we find that reducing $T$ makes the link
capacity more variable on the base RTT time scale and the performance gains
are sub-linear.

Figure 12. Performance curve for optimal control law from the MIF model for
different values of $T$— The difference in solid and the dashed line for a
particular color shows that reducing $T$ has diminishing returns.

##  Appendix D MIF Model Proofs

This section includes proofs from main body for the MIF model (§4). Assuming
the terminology established in §3 and §4.

###  D.1. Proof of Lemma 2

###### Proof.

We will first calculate the slope of the function $g^{f}(\cdot)$.
Differentiating $x$ and $g^{f}(x)$ with respect to $b$ using the Leibniz
integral rule,

$\displaystyle\frac{dx}{db}$
$\displaystyle=T\cdot\frac{d\left(\int_{0}^{b}\left(\frac{b}{a}-1\right)\cdot
f(a)\cdot da\right)}{db},$
$\displaystyle=T\cdot\left(\int_{0}^{b}\frac{f(a)}{a}\cdot dx\right),$
$\displaystyle\frac{d(g^{f}(x))}{db}$
$\displaystyle=\frac{d\left(\int_{b}^{\infty}\left(1-\frac{b}{a}\right)\cdot
f(a)\cdot da\right)}{db},$ (51)
$\displaystyle=-\int_{b}^{\infty}\frac{f(a)}{a}\cdot da.$

Combining the equations above we get,

(52) $\displaystyle\frac{d(g^{f}(x))}{dx}$
$\displaystyle=-\frac{\int_{b}^{\infty}\frac{f(a)}{a}\cdot
da}{T\cdot\left(\int_{0}^{b}\frac{f(a)}{a}\cdot da\right)}.$

Note that in the above equation the denominator is increasing with $b$ while
the absolute value of the numerator is decreasing. This implies that as we
increase $b$ (and consequently $x$) the absolute slope of the function
$g^{f}(\cdot)$ is decreasing (or the slope is increasing) with $x$. Therefore,
the function is convex irrespective of the PDF $f$. Since the curve
$g^{f}(\cdot)$ forms the boundary of $\mathbb{C}^{f}$, $\mathbb{C}^{f}$is
convex. ∎

###  D.2. Proof of Proposition 3

###### Proof.

We will first show that if the Proposition condition holds then with the
policy $\rho(t)=C$, $Q(t)\leq T\cdot C\cdot\mu(t)$ $\forall t\in\mathbb{N}$.
We will prove this by induction.

The base case holds because $Q(0)=0$. Lets assume that $Q(t-1)\leq T\cdot
C\cdot\mu(t-1)$, then we can pick a non negative $s(t)$, such that
$\rho(t)=C$. Then in the next time step $t$,

$\displaystyle Q(t)$ $\displaystyle=(Q(t-1)+s(t)\cdot T-\mu(t)\cdot T)^{+},$
$\displaystyle=(T\cdot C\cdot\mu(t-1)-T\cdot\mu(t))^{+},$
$\displaystyle=T\cdot
C\cdot\mu(t)\cdot\left(\frac{1}{X_{t}}-\frac{1}{C}\right)^{+},$
$\displaystyle\leq T\cdot
C\cdot\mu(t)\cdot\left(\frac{1}{X_{min}}-\frac{1}{C}\right)^{+},$ (53)
$\displaystyle\leq T\cdot\mu(t)\cdot C,$

where in the last step we used Eq. (18).

The above equation also shows that if the Proposition condition does not hold
then, $Q(t)$ will exceed $T\cdot C\cdot\mu(t)$ with non-zero probability($\geq
P(X_{t}<C/(C+1)$). Consequently, the sender will not always be able follow
$\rho(t+1)=C$ in time step $t+1$. Proposition proved.

∎

###  D.3. Proof of Lemma 5

###### Proof.

To prove this Lemma, we will first reconsider a variant of the MDP over a
finite number of time steps $n$.For the finite time steps version, we can
define the optimal value function at the start of time step $t$
($V_{t}(\cdot)$) as follows,

(54) $\displaystyle
V_{t}(q,\mu)=\min_{\pi}E\left[\sum_{i=t}^{n}\gamma^{i-t}\Big{(}w\cdot
q(i)+U(i)]\Big{)}\Bigg{|}q(t-1)=q,\mu(t-1)=\mu,s(t)\sim\pi\right].$

We will show that $V_{t}(q,u)$ is independent of $\mu$ (Lemma 1) and convex as
a function of $q$ (Lemma 2). We close the proof by considering this MDP over
infinite horizon ($n\to\infty$). By definition, as $n\to\infty,V_{t}(q,\mu)\to
V(q,u)$ and Lemma proved. ∎

The bellman equation for the finite time steps MDP is as follows,

$\displaystyle V_{t}(q,\mu)$ $\displaystyle=\min_{s(t)\geq 0}E\left[w\cdot
q(t)+U(t)+\gamma\cdot
V_{t+1}(q(t),\mu(t))\big{|}q(t-1)=q,\mu(t-1)=\mu\right],$
$\displaystyle\forall t\leq n,$ (55) $\displaystyle V_{t}(q,\mu)$
$\displaystyle=0,$ $\displaystyle t=n+1.$

The condition $s(t)\geq 0$ is equivalent to $\rho(t)\geq\frac{q(t-1)}{T}$.
Rewriting,

$\displaystyle V_{t}(q,\mu)$
$\displaystyle=\min_{\rho(t)\geq\frac{q}{T}}E\left[w\cdot
q(t)+U(t)+\gamma\cdot
V_{t+1}(q(t),\mu(t))\big{|}q(t-1)=q,\mu(t-1)=\mu\right],$
$\displaystyle\forall t\leq n,$

###### Lemma 0.

$V_{t}(q,u)$ is independent of $\mu$, $\forall t\leq n$.

###### Proof.

In the Eq. (LABEL:eq:model1:conjecture), the first two terms on the right hand
side ($w\cdot q(t)$ and $U(t)$) depend only on the value of $\rho(t)$. Since
$q(t)$ only depends on $\rho(t)$, this implies that if $V_{t+1}(q(t),\mu(t))$
is only a function of $q(t)$ and independent of $\mu(t)$, then $V_{t}(q,\mu)$
is also only a function of $q$. Since $V_{n+1}(\cdot)$ is independent of
$\mu(n)$, then, $\forall t\leq n$ ,we can describe the function $V_{t}(q,\mu)$
using only $q$. Lemma proved.

∎

Using the above Lemma, we can rewrite Eq. (LABEL:eq:model1:conjecture),

(57) $\displaystyle V_{t}(q)$
$\displaystyle=\min_{\rho(t)\geq\frac{q}{T}}E\left[w\cdot
q(t)+U(t)+\gamma\cdot V_{t+1}(q(t))\big{|}q(t-1)=q\right],$
$\displaystyle\forall t\leq n.$

Next, we will show that $V_{t}(\cdot)$ is convex.

###### Lemma 0.

$\forall t\leq n$, $V_{t}(\cdot)$ is convex.

###### Proof.

We give an induction based proof for the Lemma. We will show that if
$V_{t+1}(\cdot)$ is convex then $V_{t}(\cdot)$ is convex. Our proof exploits
the fact that $E[q(t)|\rho(t)]$ and $E[U(t)|\rho(t)]$ are both convex as a
function of $\rho(t)$.

To prove this Lemma, we will first prove three other Sub Lemmas. To help our
analysis, we define a new helper function $W_{t}(\cdot)$ as follows,

$\displaystyle W_{t}(\rho)$ $\displaystyle=E\left[w\cdot q(t)+U(t)+\gamma\cdot
V_{t+1}(q(t))\big{|}\rho(t)=\rho\right],$ $\displaystyle\forall t\leq n,$ (58)
$\displaystyle V_{t}(q)$
$\displaystyle=\min_{\rho\geq\frac{q}{T}}(W_{t}(\rho)),$ $\displaystyle\forall
t\leq n.$

Expanding $V_{t+1}(q(t))$ in the equation above, we can rewrite $W_{t}$ as
follows,

(60) $\displaystyle W_{t}(\rho)$ $\displaystyle=(w\cdot
E[q(t)|\rho(t)=\rho]+E[U(t)|\rho(t)=\rho])+\gamma\cdot\int_{0}^{\infty}\left(f(a)\cdot
V_{t+1}\left(T\cdot\left(\frac{\rho}{a}-1\right)^{+}\right)\cdot da\right),$
$\displaystyle\forall t\leq n.$

###### Sub Lemma 0.1.

$\forall t\leq n$, if $W_{t}(\cdot)$ is convex then $V_{t}(\cdot)$ is convex.

###### Proof.

To prove this Sub Lemma we will show

(61) $\displaystyle V_{t}(\alpha\cdot x+(1-\alpha)\cdot y)$
$\displaystyle\leq\alpha\cdot V_{t}(x)+(1-\alpha)V_{t}(y),$
$\displaystyle\forall\alpha\in[0,1],x,y\in\mathbb{R}^{+},x<y.$

Let’s assume that minima of $W_{t}(\cdot)$ occurs at $\rho=C$ (need not be
unique). Since $W_{t}(\cdot)$ is convex,

$\displaystyle W_{t}(x)$ $\displaystyle\geq W_{t}(C),$ $\displaystyle\forall
x\geq C,$ $\displaystyle\Rightarrow V_{t}(T\cdot x)$ $\displaystyle=W_{t}(x),$
$\displaystyle\forall x\geq C,$ $\displaystyle W_{t}(x)$ $\displaystyle\leq
W_{t}(C),$ $\displaystyle\forall x<C,$ (62) $\displaystyle\Rightarrow
V_{t}(T\cdot x)$ $\displaystyle=W_{t}(C),$ $\displaystyle\forall x<C.$

Lets define a new function $h(\cdot)$,

$\displaystyle h(x)$ $\displaystyle=\frac{x}{T},$ $\displaystyle\forall x\geq
C\cdot T,$ $\displaystyle h(x)$ $\displaystyle=\frac{C}{T},$
$\displaystyle\forall x<C\cdot T,$ (63) $\displaystyle\Rightarrow V_{t}(x)$
$\displaystyle=W_{t}(h(x)).$

Note that $h(\cdot)$ is convex. Since, $h(x)\geq C\forall x\in\mathbb{R}^{+}$
and $W_{t}(x)\geq W_{t}(y),\forall x\geq y\geq C$, we can write,

$\displaystyle h(\alpha\cdot x+(1-\alpha)\cdot y)$
$\displaystyle\leq\alpha\cdot h(x)+(1-\alpha)\cdot h(y),$ (64)
$\displaystyle\Rightarrow W_{t}(h(\alpha\cdot x+(1-\alpha)\cdot y))$
$\displaystyle\leq W_{t}(\alpha\cdot h(x)+(1-\alpha)\cdot h(y)).$

Using this,

$\displaystyle V_{t}(\alpha\cdot x+(1-\alpha)\cdot y)$
$\displaystyle=W_{t}(h(\alpha\cdot x+(1-\alpha)\cdot y)),$ $\displaystyle\leq
W_{t}(\alpha\cdot h(x)+(1-\alpha)\cdot h(y)),$ $\displaystyle\leq\alpha\cdot
W_{t}(h(x))+(1-\alpha)\cdot W_{t}(h(y)),$ (65) $\displaystyle=\alpha\cdot
V_{t}(x)+(1-\alpha)\cdot V_{t}(y).$

Sub Lemma proved. ∎

###### Sub Lemma 0.2.

$\forall t\leq n$, $V_{t}(\cdot)$ is non-decreasing, i.e., if $x\leq y$, then,
$V_{t}(x)\leq V_{t}(y)$.

###### Proof.

Lets assume that for $V_{t}(y)$ minima occurs at $\rho(t)=C_{y}$. Since
$C_{y}\geq\frac{y}{T}$, $C_{y}\geq\frac{x}{T}$. Thus, for $V_{t}(x)$ we can
always pick $\rho(t)=C_{y}$, and, $V_{t}(x)$ is upper bounded by $V_{t}(y)$.
Sub lemma proved. ∎

###### Sub Lemma 0.3.

$\forall t\leq n$, if $V_{t+1}(\cdot)$ is convex, then $W_{t}(\cdot)$ is
convex.

###### Proof.

Lets define $h_{a}(\cdot)$ as follows,

(66) $\displaystyle h_{a}(x)=T\cdot\left(\frac{x}{a}-1\right)^{+}.$

The functions $h_{a}(\cdot)$ are convex $\forall a\in\mathbb{R}^{+}$.
Rewriting Eq. (60),

$\displaystyle W_{t}(x)$ $\displaystyle=(w\cdot
E[q(t)|\rho(t)=x]+E[U(t)|\rho(t)=x])+\int_{0}^{\infty}\left(f(a)\cdot
V_{t+1}(h_{a}(x))\cdot da\right),$ $\displaystyle\forall t\leq n.$

Since $h_{a}(\cdot)$ is convex, and $V_{t+1}(\cdot)$ in convex and non-
decreasing, $V_{t+1}\circ h_{a}(\cdot)$ is convex. Additionally
$E[q(t)|\rho(t)=x]$ and $E[U(t)|\rho(t)=x]$ are also convex in $x$ (Lemma 2
and Eq. (14)). Since summation of convex functions is convex, $W_{t}(\cdot)$
is convex. Sub lemma proved. ∎

The last three Sub lemmas, prove that $\forall t\leq n$ if $V_{t+1}(\cdot)$ is
convex then $V_{t}(\cdot)$ is convex. Since $V_{n+1}(\cdot)$ is convex by
definition, Lemma proved. ∎

##  Appendix E PMIF Model Proofs

This section includes proofs from main body for the PMIF model (§4.4).
Assuming the terminology established §3 and §4.4.

###  E.1. Proof of Corollary 8

###### Proof.

Define the optimal value function for our MDP as:

(68) $\displaystyle
V^{p}\left(q,\mu,Pred\right)=\min_{\pi}E\left[\sum_{t=1}^{\infty}\gamma^{t-1}\Big{(}w\cdot
q(t)+U(t)]\Big{)}\Bigg{|}q(0)=q,\mu(0)=\mu,Pred(0)=Pred,s(t)\sim\pi\right].$

We only consider $f^{p}(\cdot)$ for which $V(q,\mu,Pred)$ exists.

For ease of analysis, we introduce an additional variable $Q/Pred$ in the
optimal value function as the state. Rewriting the equation above,

$\displaystyle
V^{p}\left(q,\mu,Pred,\frac{Q}{Pred}\right)=\min_{\pi}E\Bigg{[}$
$\displaystyle\sum_{t=1}^{\infty}\gamma^{t-1}\Big{(}w\cdot
q(t)+U(t)]\Big{)}\Bigg{|}$ (69) $\displaystyle
q(0)=q,\mu(0)=\mu,Pred(0)=Pred,\frac{Q(0)}{Pred(0)}=\frac{Q}{Pred},s(t)\sim\pi\Bigg{]}.$

The condition $s(t)\geq 0$ translates to $\rho^{p}(t)\geq\frac{Q(t-1)}{T\cdot
Pred(t-1)}$. The optimal value function thus satisfies the following Bellman
Equation:

$\displaystyle
V^{p}\left(q,\mu,Pred,\frac{Q}{Pred}\right)=\min_{\rho^{p}(1)\geq\frac{Q}{T\cdot
Pred}}E\Bigg{[}$ $\displaystyle w\cdot q(1)+U(1)+\gamma
V^{p}\left(q(1),\mu(1),Pred(1),\frac{Q(1)}{Pred(1)}\right)\Bigg{|}$ (70)
$\displaystyle
q(0)=q,\mu(0)=\mu,Pred(0)=Pred,\frac{Q(0)}{Pred(0)}=\frac{Q}{Pred}\Bigg{]}.$

###### Lemma 0.

$V^{p}(q,\mu,Pred,\frac{Q}{Pred})$ is a convex function of $\frac{Q}{Pred}$
and does not depend on $q,\mu,Pred$.

###### Proof.

Again, we reconsider a variant of this MDP over a finite number of time steps
$n$.For the finite time steps version, we can define the optimal value
function at the start of time step $t$ ($V^{p}_{t}(\cdot)$) as follows,

$\displaystyle
V^{p}_{t}\left(q,\mu,Pred,\frac{Q}{Pred}\right)=\min_{\pi}E\Bigg{[}$
$\displaystyle\sum_{i=t}^{n}\gamma^{i-t}\Big{(}w\cdot
q(i)+U(i)]\Big{)}\Bigg{|}$ (71) $\displaystyle
q(t-1)=q,\mu(t-1)=\mu,Pred(t-1)=Pred,\frac{Q(t-1)}{Pred(t-1)}=\frac{Q}{Pred},s(t)\sim\pi\Bigg{]}.$

We will show that $V^{p}_{t}(q,u,Pred,\frac{Q}{Pred})$ is independent of
$q,\mu,pred$ (Lemma 2) and convex as a function of $\frac{Q}{Pred}$ (Lemma 3).
We close the proof by considering this MDP over infinite horizon
($n\to\infty$). By definition, as
$n\to\infty,V^{p}_{t}(q,\mu,Pred,\frac{Q}{Pred})\to
V^{p}(q,\mu,pred,\frac{Q}{Pred})$ and Lemma proved. ∎

The Bellman Equation for the finite time steps MDP is as follows,

$\displaystyle
V^{p}_{t}\left(q,\mu,Pred,\frac{Q}{Pred}\right)=\min_{\rho^{p}(t)\geq\frac{Q}{T\cdot
Pred}}E\Bigg{[}$ $\displaystyle w\cdot q(t)+U(t)+\gamma\cdot
V^{p}_{t+1}\left(q(t),\mu(t),Pred(t),\frac{Q(t)}{Pred(t)}\right)\Bigg{|}$
$\displaystyle q(t-1)=q,\mu(t-1)=\mu,$ $\displaystyle
Pred(t-1)=Pred,\frac{Q(t-1)}{Pred(t-1)}=\frac{Q}{Pred}\Bigg{]},$
$\displaystyle\forall t\leq n,$ (72) $\displaystyle
V^{p}_{t}\left(q,\mu,Pred,\frac{Q}{Pred}\right)$ $\displaystyle=0,$
$\displaystyle t=n+1.$

###### Lemma 0.

$V^{p}_{t}(q,u,pred,\frac{Q}{pred})$ is independent of $q,\mu,pred$, $\forall
t\leq n$.

###### Proof.

Now,

(73)
$\displaystyle\frac{Q(t)}{Pred(t)}=T\cdot\left(\frac{\rho^{p}(t)}{X^{p}_{t}}-1\right)^{+}\cdot\frac{X^{p}_{t}}{X^{pred}_{t}}$

In the Eq. (72), the first two terms on the right hand side ($w\cdot q(t)$ and
$U(t)$) depend only on the value of $\rho^{p}(t)$. Since $Q(t)/Pred(t)$ also
only depends on $\rho^{p}(t)$, this implies that if
$V^{p}_{t+1}(q(t),\mu(t),Pred(t),Q(t)/Pred(t)$ is only a function of
$Q(t)/Pred(t)$, then $V^{p}_{t}(q,\mu)$ is also only a function of $q$. Since
$V^{p}_{n+1}(\cdot)$ is independent of $q(n),\mu(n),Pred(n)$, then, $\forall
t\leq n$ ,we can describe the function $V^{p}_{t}(q,\mu,Pred,\frac{Q}{Pred})$
using only $Q/Pred$. Lemma proved.

∎

Using the above Lemma, we can rewrite Eq. (72),

(74) $\displaystyle V^{p}_{t}\left(\frac{Q}{Pred}\right)$
$\displaystyle=\min_{\rho^{p}(t)\geq\frac{Q}{T\cdot Pred}}E\left[w\cdot
q(t)+U(t)+\gamma\cdot
V_{t+1}\left(\frac{Q(t)}{Pred(t)}\right)\Bigg{|}\frac{Q(t-1)}{Pred(t-1)}=\frac{Q}{Pred}\right],$
$\displaystyle\forall t\leq n.$

###### Lemma 0.

$\forall t\leq n$, both $V^{p}_{t}(\cdot)$ is convex.

###### Proof.

To help our analysis, we define a new helper function $W_{t}(\cdot)$ as
follows,

$\displaystyle W^{p}_{t}(\rho^{p})$ $\displaystyle=E\left[w\cdot
q(t)+U(t)+\gamma\cdot
V^{p}_{t+1}\left(\frac{Q(t)}{Pred(t)}\right)\Big{|}\rho^{p}(t)=\rho^{p}\right],$
$\displaystyle\forall t\leq n,$ (75) $\displaystyle
V^{p}_{t}\left(\frac{Q}{Pred}\right)$
$\displaystyle=\min_{\rho^{p}\geq\frac{Q}{T\cdot Pred}}(W^{p}_{t}(\rho^{p})),$
$\displaystyle\forall t\leq n.$

Expanding $V^{p}_{t+1}(\frac{Q(t)}{Pred(t)})$ in the equation above, we can
rewrite $W^{p}_{t}$ as follows,

$\displaystyle W^{p}_{t}(\rho^{p})=w\cdot E[$ $\displaystyle
q(t)|\rho^{p}(t)=\rho^{p}]+E[U(t)|\rho^{p}(t)=\rho^{p}]$
$\displaystyle+\gamma\cdot\int_{0}^{\infty}\int_{0}^{\infty}\Big{(}f^{p}(a)\cdot
f^{pred}(b)\cdot
V^{p}_{t+1}\left(T\cdot\left(\frac{\rho^{p}}{a}-1\right)^{+}\cdot\frac{a}{b}\right)\cdot
da\cdot db\Big{)}$ $\displaystyle,\forall t\leq n$

The remainder of proof for this lemma is similar to proof of Lemma 2, except
we need to redefine $h_{a}(\cdot)$ from Sub lemma 0.3 as follows.

(78) $\displaystyle
h_{a,b}(x)=T\cdot\left(\frac{x}{a}-1\right)^{+}\cdot\frac{a}{b}$

$V^{p}_{t+1}\circ h_{a,b}$ is also convex. ∎

To close the proof of the corollary, we exploit the fact that $q(t),U(t)$ and
$\frac{Q(1)}{Pred(1)}$ only depend on the value of $\rho^{p}(t)$, and define a
helper function $W(\cdot)$ as follows,

$\displaystyle W(\rho^{p})$ $\displaystyle=E\left[w\cdot q(1)+U(1)+\gamma\cdot
V^{p}\left(\frac{Q(1)}{Pred(1)}\right)\Bigg{|}\rho^{p}(1)=\rho^{p}\right]$
(79) $\displaystyle V^{p}\left(\frac{Q}{Pred}\right)$
$\displaystyle=\min_{\rho^{p}\geq\frac{Q}{T\cdot Pred}}(W^{p}(\rho^{p})).$

In other words, $W^{p}(\rho^{p})$ is the optimal value function restricting
the first action $\rho^{p}(1)$ to $\rho^{p}$.

###### Lemma 0.

$W^{p}(\rho^{p})$ is a convex function in $\rho^{p}$.

###### Proof.

The proof directly follows from proof of Sub lemma 0.3 in Appendix D.3. ∎

Let the minimum value of $W^{p}(\cdot)$ occur at $\rho^{p*}$. Then, the
convexity of $W^{p}(\cdot)$ combined with Eq. (79) establishes that the
optimal control law is of the form
$\rho^{p}(t)=max(\rho^{p*},\frac{Q(t-1)}{T\cdot Pred(t-1)})$, where
$\rho^{p*}$ depends on $w$ and $\gamma$. Defining $C^{p}(w,\gamma)=\rho^{p*}$,
we get the optimal control law from the corollary.

∎

##  Appendix F SMF Model Proofs

This section includes proofs from main body for the SMF model (§6). Assuming
the terminology established §3 and §6.

###  F.1. Proof of Proposition 3

###### Proof.

To prove this Proposition, we will first show that if $y=g^{A}(x)$, then
$g^{f^{i}}{{}^{\prime}}(x^{i})=g^{f^{j}}{{}^{\prime}}(x^{j}),\forall
i,j\in\textbf{S}$. We will prove this by contradiction. Lets assume,
$g^{f^{i}}{{}^{\prime}}(x^{i})<g^{f^{j}}{{}^{\prime}}(x^{j})$. Then, we can
pick a new point $(x_{1},y_{1})$ ($x_{1}=\sum_{k\in\textbf{S}}\lambda(i)\cdot
x_{1}^{k},y_{1}=\sum_{k\in\textbf{S}}\lambda(i)\cdot y_{1}^{k}$) such that

$\displaystyle y_{1}^{k}$ $\displaystyle=g^{f^{k}}(x_{1}^{k}),$
$\displaystyle\forall k\in\textbf{S},$ $\displaystyle x_{1}^{k}$
$\displaystyle=x^{k},$ $\displaystyle\forall k\in\textbf{S}-\\{i,j\\},$
$\displaystyle\Rightarrow y_{1}^{k}$ $\displaystyle=g^{f^{k}}(x^{k}),$
$\displaystyle\forall k\in\textbf{S}-\\{i,j\\},$ $\displaystyle x_{1}^{i}$
$\displaystyle=x^{i}+\frac{\epsilon}{\lambda(i)},$ $\displaystyle\Rightarrow
y_{1}^{i}$
$\displaystyle=y^{i}+\frac{\epsilon}{\lambda(i)}g^{f^{i}}{{}^{\prime}}(x^{i}),$
$\displaystyle if\epsilon\to 0,$ $\displaystyle x_{1}^{j}$
$\displaystyle=x^{j}-\frac{\epsilon}{\lambda(j)},$ (80)
$\displaystyle\Rightarrow y_{1}^{j}$
$\displaystyle=y^{j}-\frac{\epsilon}{\lambda(j)}g^{f^{j}}{{}^{\prime}}(x^{j}),$
$\displaystyle if\epsilon\to 0.$

If $\epsilon\to 0$, then $(x_{1},y_{1})$ can be given by

$\displaystyle x_{1}$
$\displaystyle=\left(\sum_{k\in\textbf{S}}\lambda(k)\cdot
x^{k}\right)+\lambda(i)\cdot\frac{\epsilon}{\lambda(i)}-\lambda(j)\cdot\frac{\epsilon}{\lambda(j)},$
$\displaystyle=x,$ $\displaystyle y_{1}$
$\displaystyle=\left(\sum_{k\in\textbf{S}}\lambda(k)\cdot
g^{i}(x^{i})\right)+\lambda(i)\cdot\frac{\epsilon}{\lambda(i)}\cdot
g^{f^{i}}{{}^{\prime}}(x^{i})-\lambda(j)\cdot\frac{\epsilon}{\lambda(j)}\cdot
g^{f^{j}}{{}^{\prime}}(x^{j}),$ (81)
$\displaystyle=y+\epsilon\cdot(g^{f^{i}}{{}^{\prime}}(x^{i})-g^{f^{j}}{{}^{\prime}}(x^{j})).$

Since $x_{1}=x$ and $y_{1}<y$, the point $(x,y)$ cannot be on the boundary.
Contradiction.

Finally, we will show that if the point $(x,y)$ satisfies the condition
$g^{f^{k}}{{}^{\prime}}(x^{k})=C\forall k\in\textbf{S}$, then it will be on
the boundary. To do this we will show that there does not exist another point
$(x_{1},y_{1})(x_{1}=\sum_{k\in\textbf{S}}\lambda(i)\cdot
x_{1}^{k},y_{1}=\sum_{k\in\textbf{S}}\lambda(i)\cdot g^{f^{k}}(x^{k}_{1})$)
which satisfies the condition $g^{f^{k}}{{}^{\prime}}(x_{1}^{k})=C_{1}$,
$\forall k\in\textbf{S}$ and $x=x_{1}$ but $y_{1}<y$. Lets assume $C<C1$.
Since $g^{f^{k}}$ in convex with increasing slope,

$\displaystyle g^{f^{k}}{{}^{\prime}}(x^{k})$
$\displaystyle<g^{f^{k}}{{}^{\prime}}(x_{1}^{k}),$ $\displaystyle\forall
k\in\textbf{S},$ $\displaystyle\Rightarrow x^{k}$ $\displaystyle<x_{1}^{k},$
$\displaystyle\forall k\in\textbf{S},$ (82) $\displaystyle\Rightarrow x$
$\displaystyle<x_{1}.$

Since $x<x_{1}$, we have a contradiction. We can show a similar contradiction
if $C>C1$ (we will get $x>x_{1}$). For $C=C_{1}$, since $g^{f^{k}}(\cdot)$ is
convex, if $x=x_{1}$, then $y=y_{1}$. This is because

$\displaystyle g^{f^{k}}(x_{1}^{k})$
$\displaystyle=g^{f^{k}}(x^{k}+(x_{1}^{k}-x^{k})),$ $\displaystyle\forall
k\in\textbf{S},$
$\displaystyle=g^{f^{k}}(x^{k})+g^{f^{k}}{{}^{\prime}}\cdot(x_{1}^{k}-x^{k}),$
$\displaystyle\forall k\in\textbf{S},$
$\displaystyle=g^{f^{k}}(x^{k})+C\cdot(x_{1}^{k}-x^{k}),$
$\displaystyle\forall k\in\textbf{S},$ $\displaystyle y_{1}$
$\displaystyle=\sum_{k\in\textbf{S}}g^{f^{k}}(x^{k}_{1})=y+C\cdot\sum_{k\in\textbf{S}}(x_{1}^{k}-x^{k}),$
(83) $\displaystyle\Rightarrow y_{1}$ $\displaystyle=y.$

Proposition proved! ∎

###  F.2. Proof of Proposition 4

###### Proof.

First, we will show that if the Theorem condition holds then with the policy
$\rho(t)=C^{A}(S(t-1))$, $Q(t)\leq T\cdot C^{A}(S(t))\cdot\mu(t)$ $\forall
t\in\mathbb{N},\forall S(t-1)\in\textbf{S}$. We will prove the Proposition
using induction

Base case holds as Q(0) = 0. Lets assume that $Q(t-1)\leq T\cdot
C^{A}(S(t-1))\cdot\mu(t-1)$ $\forall S(t-1)\in\textbf{S}$, then $\forall
S(t)\in\textbf{S}$, we can pick a non negative $s(t)$, such that
$\rho(t)=C^{A}(S(t-1))$. Then in the next time step $t$,

$\displaystyle Q(t)$ $\displaystyle=(Q(t-1)+s(t)\cdot T-\mu(t)\cdot T)^{+},$
$\displaystyle=(T\cdot C^{A}(S(t-1))\cdot\mu(t-1)-T\cdot\mu(t))^{+},$
$\displaystyle=T\cdot
C^{A}(S(t))\cdot\mu(t)\cdot\left(\frac{C^{A}(S(t-1))}{C^{A}(S(t))\cdot
X^{S(t-1)}_{t}}-\frac{1}{C^{A}(S(t))}\right)^{+},$ (84) $\displaystyle\leq
T\cdot C^{A}(S(t))\cdot\mu(t)\cdot\left(\frac{C^{A}(S(t-1))}{C^{A}(S(t))\cdot
X^{S(t-1)}_{min}}-\frac{1}{C^{A}(S(t))}\right)^{+}.$

Rewriting the Proposition condition using $k_{1}=S(t-1)$ and $k_{2}=S(t)$,

$\displaystyle\frac{C^{A}(S(t-1))}{C^{A}(S(t))\cdot
X^{S(t-1)}_{min}}-\frac{1}{C^{A}(S(t))}$ $\displaystyle\leq 1,$ (85)
$\displaystyle\Rightarrow Q(t)$ $\displaystyle\leq T\cdot\mu(t)\cdot
C^{A}(S(t)).$

The above analysis also shows that if the Proposition condition does not hold
then, $Q(t)$ will exceed $T\cdot C^{A}(S(t))\cdot\mu(t)$ with non-zero
probability. Consequently, the sender will not always be able follow
$\rho(t+1)=C^{A}(S(t))$ in time step $t+1$. Proposition proved.

∎

###  F.3. Proof of Corollary 5

###### Proof.

Define the optimal value function for our MDP as:

(86) $\displaystyle
V^{A}(q,\mu,k)=\min_{\pi}E\left[\sum_{t=1}^{\infty}\gamma^{t-1}\Big{(}w\cdot
q(t)+U(t)]\Big{)}\Big{|}q(0)=q,\mu(0)=\mu,S(0)=k,s(t)\sim\pi\right].$

We only consider $\cup_{k\in\textbf{S}}f^{k}(\cdot)$ such that
$V^{A}(q,\mu,k)$ exists.

The optimal value function satisfies the following Bellman Equation:

(87) $\displaystyle V^{A}(q,\mu,k)=\min_{\rho(1)\geq\frac{q}{T}}E\left[w\cdot
q(1)+U(1)+\gamma
V^{A}(q(1),\mu(1),S(1))\Big{|}q(0)=q,\mu(0)=\mu,S(0)=k,\right].$

###### Lemma 0.

$V^{A}(q,\mu,k)$ is a convex function of $q$ and does not depend on $\mu$.

###### Proof.

The proof for this lemma is analogous to proof of Lemma 5. Again, we can
define the optimal value function in time step $t$ $V^{A}_{t}(\cdot)$ for the
finite time steps version of the MDP. The Bellman Equation for
$V^{A}_{t}(\cdot)$ is as follows,

$\displaystyle
V^{A}_{t}(q,\mu,k)=\min_{\rho(t)\geq\frac{q}{T}}E\Bigg{[}\Big{(}$
$\displaystyle w\cdot
q(t)+U(t)+\gamma\cdot\sum_{S(t)\in\textbf{S}}P^{A}(S(t)|S(t-1))\cdot
V^{A}_{t+1}(q(t),\mu(t),S(t))\Big{)}\Bigg{|}$ $\displaystyle
q(t-1)=q,\mu(t-1)=\mu,S(t-1)=k\Bigg{]},$ $\displaystyle\forall t\leq n,\forall
k\in\textbf{(}S)$ (88) $\displaystyle V^{A}_{t}(q,\mu,k)$ $\displaystyle=0,$
$\displaystyle t=n+1,\forall k\in\textbf{S}.$

Using the proof of Lemma 2, we can show that the $V^{A}_{t}(q,\mu,k)$ is a
convex function of $q$ and does not depend on $\mu$. The key change in the
induction step is that if $V^{A}_{t+1}(q,\mu,k)$ is convex in $q,\forall
k\in\textbf{S}$, then, $V^{A}_{t}(q,\mu,k)$ is convex in $q,\forall
k\in\textbf{S}$.

Consequently, $V^{A}(q,\mu,k)$ is a convex function of $q$ and does not depend
on $\mu$. ∎

To close the proof of the corollary, we exploit the fact that $q(t),U(t)$ and
$S(t)$ only depend on the value of $\rho(t)andS(t-1)$ and define a helper
function $W^{A}(\cdot)$ as follows,

$\displaystyle W^{A}(\rho,k)$ $\displaystyle=E\left[w\cdot
q(1)+U(1)+\gamma\cdot V^{A}(q(1),S(1))\big{|}\rho(1)=\rho,S(0)=k\right]$ (89)
$\displaystyle V^{A}(q,k)$
$\displaystyle=\min_{\rho\geq\frac{q}{T}}(W^{A}(\rho,k)).$

In other words, $W^{A}(\rho,k)$ is the optimal value function restricting the
first action $\rho(1)$ to $\rho$ and link state $S(0)$ to $k$.

###### Lemma 0.

$\forall k\in\textbf{S},W^{A}(\rho,k)$ is a convex function in $\rho$.

###### Proof.

The proof is analogous to proof of Sub lemma 0.3 in Appendix D.3. ∎

Given a $k$, let the minimum value of $W^{A}(x,k)$ occur at $\rho^{k*}$. Then,
the convexity of $W^{A}(\cdot)$ combined with Eq. (89) establishes that the
optimal control law is of the form
$\rho(t)|(S(t-1)=k)=max(\rho^{k*},\frac{q(t-1)}{T})$, where $\rho^{k*}$
depends on $w$ and $\gamma$. Defining $C^{A}(w,\gamma,k)=\rho^{k*}$, we get
the optimal control law from the corollary.

∎

##  Appendix G Stability in Continuous-time domain

Let $\mu_{I}(t),s_{I}(t),q(t)_{I}(t),Q_{I}(t)$ be the instantaneous link
capacity, sending rate, queuing delay and queue size respectively. Assuming
$\mu_{I}(t)=\mu$ for $t>t_{0}$, then for $t>t_{0}+T$, the optimal control law
in all our models will be of the form,

(90) $\displaystyle s_{I}(t)=\left(C-\frac{Q_{I}(t-T)}{T}\right)^{+},$

where $C$ is a positive constant depending on the $\mu$ and the model.

###### Proposition 0.

For a single bottleneck time-varying link, the control law from Eq. (90) is
globally asymptotically stable, $\forall C\in\mathbb{R}^{+}$.

###### Proof.

To prove this Proposition, we leverage the proof of stability for the ABC
control law (see Appendix C in [8]). Similar to ABC, ignoring the boundary
condition (${q}_{I}(t)$ must be $\geq 0$), we can describe the rate of change
of queuing delay as follows,

$\displaystyle\dot{q}_{I}(t)$ $\displaystyle=\frac{s_{I}(t)-\mu}{\mu},$
$\displaystyle\dot{q}_{I}(t)$
$\displaystyle=\left(\frac{C}{\mu}-\frac{q_{I}(t-T)}{T}\right)^{+}-1,$ (91)
$\displaystyle\dot{q}_{I}(t)$
$\displaystyle=max\left(\left(\left(\frac{C}{\mu}-1\right)-\frac{q_{I}(t-T)}{T}\right),-1\right).$

Lets define $x(t)=q_{I}(t)-T\cdot(\frac{C}{\mu}-1)$, then,

$\displaystyle\dot{x}(t)=max\left(-\frac{x(t-T)}{T},-1\right),$
$\displaystyle\dot{x}(t)=-min\left(\frac{x(t-T)}{T},1\right),$ (92)
$\displaystyle\dot{x}(t)=-g(x(t-T)),$

where $g(u)=min(\frac{u}{T},1)$.

In [39] (Corollary 3.1), Yorke established that delay-differential equations
of this type are globally asymptotically stable (i.e., ${x}(t)\to 0$ as
$t\to\infty$ irrespective of the initial condition), if the following
conditions are met:

  1. (1)

H1: g is continuous.

  2. (2)

H2: There exists some $\alpha$, s.t. $\alpha\cdot u^{2}>ug(u)>0$ for all
$u\neq 0$.

  3. (3)

H3: $\alpha\cdot T<\frac{3}{2}$.

The function $g(\cdot)$ trivially satisfies H1.
$\alpha\in(\frac{1}{T},\frac{3}{2\cdot T})$ satisfies both H2 and H3.

∎