# Hercules: Heterogeneous Requirements Congestion Control Protocol

Neta Rozen-Schiff, Itzcak Pechtalt, Amit Navon and Leon Bruckman

###### Abstract

Today’s networks are struggling to scale and satisfy the high number and high
variety of co-existing network requirements. While existing congestion control
(CC) protocols are designed to handle strict classification of network flows
into one or few priorities, a more granular and dynamic congestion control is
needed.

In this paper we present Hercules, a novel CC protocol based on an online
learning approach, which supports unbounded and continues requirements space.
We implemented Hercules as a QUIC module and we show, through analytical
analysis and real-world experiments, that it provides between $50\%-250\%$
higher QoS for co-existing diverse network flows and outperforms state-of-the-
art CC protocols, even under high network congestion.

###### Index Terms:

Congestion Control, QoS requirements, QUIC

##  I Introduction

Over the years, networks are becoming faster and more reliable. However,
modern network applications have very high Quality of Service (QoS)
requirements which are still ”very challenging“ to satisfy over the _Internet_
[1]. These requirements include high reliability, low latency and high
bandwidth. Among them, bandwidth is the most heterogeneous requirement [1],
where flows bandwidths of several degrees of magnitude apart may co-exists in
the same network, for example, industrial automation with about $10$Kbps flows
and video streaming with about $100$Mbps flows (more examples [2, 3, 4, 5, 6,
7] are summarized in Fig. 1).

Improper bandwidth regulation may result in overloading outgoing buffers,
which in turn increases latency and reduces reliability. The applications
which suffer the most from QoS degradation are those with high bandwidth and
low latency requirements, such as Augmented Reality (AR), Virtual Reality
(VR), and remote surgery (grouped in a blue rectangle in Fig. 1). Regulating
bandwidth over the Internet is a key challenge of network protocols, even on
advanced $5$G/$6$G networks [8, 9].

For years, bandwidth regulation has been addressed by CC protocols such as
BBR[10], Cubic[11] and Vivace [12, 13], however these protocols address all
flows in the same manner (aiming to achieve ”fair share“) regardless of their
requirements and fail to satisfy high bandwidth requirement flows, even in
uncongested scenarios [14].

Therefore, recent works [15, 16, 17, 18, 19, 14, 20, 21, 22] explored unfair
bandwidth allocations, claiming that ”the era of friendly TCPs has been broken
down“ [19]. These works can be divided into two groups with regards to the way
they define the unfairness of the bandwidth allocation.

Figure 1: Delay, bandwidth and reliability requirements for different
applications

The first group of protocols [20, 21, 22, 13] are based on weights where the
rate of each flow is expected to be proportional to the flow’s weight divided
by the sum of all weights. While these protocols allow high degree of
granularity, they are hard to define without knowledge of the total bandwidth
and all the existing flows requirements (at any given time) which makes them
less practical in distributed environments. Even in centralized environments,
sharing weights through the network may create delays in rate adjustment [20].

The second group of protocols [17, 16, 23, 18] implement unfairness by
dividing flows into two classes: (i) primary flows that get most of the
bandwidth, and (ii) background flows, with very limited bandwidth. This
approach can’t address scenarios where there are more than two classes of flow
requirements co-existing in the same network.

In this work we present _Hercules_ , a CC protocol that provides fairness with
respect to the flow requirements. To this end, we define _Heterogeneous
Requirements based Fairness (HRF)_ which is suited for today’s network
applications. HRF prioritizes flows based on their relative requirement
satisfaction thereby providing more attention for flows with low bandwidth
requirements on the expense of high bandwidth flows. For example, control,
audio and tactile are usually more sensitive and critical than the higher
bandwidth video flows, which can reduce their resolution without significant
impact on Quality of Experience (QoE).

In summary, our key contributions are:

  * •

Leveraging insights from online-learning, we design Hercules - a provable CC
protocol which provides heterogeneous requirements based fairness.

  * •

We implemented Hercules as a CC module for QUIC.

  * •

We evaluate Hercules through theoretical analysis and real-life experiments.

  * •

We share Hercules’s code as a patch that can be easily deployed on top of
QUIC111The code will be uploaded online once the paper is accepted..

##  II Preliminaries and Motivation

In congested networks, the shared bandwidth is allocated by CC protocols that
independently run on each endpoint and regulate the sending rate of each flow.
These protocols have two main objectives: (i) fairness and (ii) high
utilization of the network resources.

The utilization objective is usually defined as reaching the Pareto efficiency
- a point (a network state) where a sender can not increase its rate without
decreasing others’. This objective alone is easy to obtain by just having each
flow increasing its sending rate until experiencing congestion, but clearly
this won’t yield a fair allocation. On the other hand, setting all sending
rates to zero can be considered fair but it clearly doesn’t utilize the
network.

In this section we discuss the different definitions for fairness which are
used by the CC protocols and see that they can lead to sub-optimal outcomes
especially for heterogeneous resources and requirements. Moreover, we discuss
the challenge of obtaining fairness.

###  II-A Existing Fairness Definitions

The most commonly used fairness objective is the Max-min fairness (MMF) [24,
25, 26, 27]. MMF is achieved by maximizing the bandwidth of the most poorly
treated flow [25]. This definition, in some cases, is not Pareto efficient,
for example, in networks with diverse flow rate constrains, MMF may impose the
rate limit of one flow on all others [28]. Moreover, MMF allocation does not
always exist [29, 30].

Lexicographic max-min fairness (LMMF) [31, 32] is a well known extension of
the max-min fairness objective in game theory. When considering flow rates as
a vector, $X=\langle x_{0},...,x_{n}\rangle$, whose elements are ordered from
low to high, LMMF is defined as the lexicographically maximal vector that can
be achieved[28]. The LMMF vector doesn’t consist of just the max min rate
($\operatorname*{arg\,max}{x_{0}}$) but also the maximums of any other rate
($x_{i}$) given the values of the lower rates ($x_{0},...,x_{i-1}$).
Therefore, LMMF achieves Pareto efficiency [33, 28, 30] and always exists (as
long as the number of flows is finite) [34].

Next we show that although LMMF resolve MMF limitations, it does not address
heterogeneous requirements of flows.

###  II-B Heterogeneous Requirements and Fairness

MMF and LMMF treat all flows equally, in the sense that they consider only
flow rates regardless of flow identities. However, today’s network
applications have different network requirements. For example, HD video
streaming with $20$Mbps flows, 3D video with $100$Mbps flows and tactile
channels with $500$Kbps flows. In many cases, these application can operate in
a wide range of bandwidths, for example video streaming may support several
picture resolutions and or frame rates. Such heterogeneous requirements, for
$n$ flows, can be defined by $(a_{i},b_{i})$ for each flow $i$, where $a_{i}$
and $b_{i}$ are the minimum and maximum bandwidth requirements respectively.
Below the minimum requirement, the application will incur significant
degradation of service quality while above the maximum requirement the
application will have no significant gain and usually will withhold from
increasing the sending rate.

As an example, in Fig. 2, we show the MMF, LMMF and optimal sending rates for
3 flows, with requirements $r_{1}=(20,30)$Mbps, $r_{2}=(40,60)$Mbps and
$r_{3}=(60,90)$Mbps and a bottleneck with capacity of 120Mbps. We can see that
with MMF (Fig.2(a)), all flows send at equal rate of $30$Mbps which doesn’t
utilise the network and doesn’t satisfies two of the flows. The LMMF
(Fig.2(b)) sending rates vector is $(30,45,45)$Mbps which fully utilizes the
network but doesn’t satisfy the third flow requirements ($r_{3}$). However, an
optimal solution (Fig.2(c)) can utilize the network and satisfy the
requirements of all flows.

To address such heterogeneous requirements a new type of fairness is needed,
one such which considers the flows requirements and make sure that in
congested scenarios at least the minimum requirement of each flow will be
satisfied (if possible). In addition, a CC protocol that provides such
fairness should be provided as well. Next, we discuss how recent CC protocols
provide existing fairness definitions.

###  II-C Congestion Control Protocols and Fairness

Congestion control protocols, such as PCC, obtain fairness by using online
learning [12, 13, 33, 18, 35, 36]. They constantly get feedback from the
network, in the form of loss ratio and RTT, regarding the current congestion
and adjust the sending rate of the endpoints. Each sender runs the protocol
independently, similarly to a the player entity in game theory. The protocol
uses a utility function in order to make a decision regarding whether and how
to change the sending rate. Such games can be proved to converge to a fair
equilibrium state [35, 37].

(a) MMF

(b) LMMF

(c) Optimal

Figure 2: $3$ fairness objectives for $3$ heterogeneous flows.

The utility function used by PCC [13] uses congestion penalties which are
based on the experienced loss and RTT obtained from ACK packets. The utility
function also accepts the sender (player) current sending rate, $x$, and
defined as follows:

$\displaystyle U(x)=(x)^{t}-x\cdot[\beta\cdot
loss-\gamma\cdot\frac{d(RTT)}{dt}],$ (1)

where $\frac{d(RTT_{i})}{dT}$ is the latency gradient, $t$ coefficient
guarantees the function concavity, and thus, the existence of an equilibrium
($0<\alpha\leq 1$). The loss coefficient $\beta\geq 0$ sets a threshold on
random loss tolerance. The latency coefficient $\gamma>0$, corresponds to a
theoretical maximum number of competing senders on a specific bottleneck with
no inflation in equilibrium state.

PCC guarantees equal sending rate for competing flows (fair-share) and was
extended to multi-path connections, by MPCC [33], which was proved to converge
to LMMF.

A simple form of heterogeneous flows was addressed in Proteus [18] by
considering two types of flows, primary and scavengers. Both flow types use a
PCC like utility functions, where scavengers are made more sensitive to
competition by an additional penalty term which is based on the RTT standard
deviation, i.e., $\sigma(RTT)$.

However, online learning approach was never extended to handle generic
scenarios with high number of heterogeneous requirement flows.

##  III Hercules Design Overview

We present Hercules, a CC protocol which extends the online learning approach
in order to guarantee convergence to fairness which considers the
heterogeneous requirements of flows. We start by defining Heterogeneous
Requirements Fairness (HRF), a fairness objective which is suited for
heterogeneous requirements. We then describe Hercules’s utility function which
converges to HRF and the rate control module which uses the utility function
to regulate sending rates.

Notation |  Description
---|---
$a_{i}$ |  Minimum requirement of flow $i$
$b_{i}$ |  Maximum requirement of flow $i$
$x_{i}$ |  Sending rate of flow $i$
$\overline{x_{i}}$ |  Relative reward of flow $i$ w.r.t its requirements.
$H(\overline{x_{i}})$ |  Requirement penalty of flow $i$ w.r.t the weighted rate.
$L_{i}$ |  Loss experienced by flow $i$
$RTT_{i}$ |  The RTT experienced by flow $i$
Table I: Notation Table

###  III-A Heterogeneous Requirements Fairness (HRF)

Existing fairness objectives, such as LMMF, were defined only in terms of flow
rates regardless flow requirements. In order to guarantee satisfaction of flow
requirements as much as possible we extend LMMF to use requirements based
normalized sending rates, i.e., for each flow $i$ with sending rate $x_{i}$ we
define the normalized rate by

$\overline{x_{i}}=\frac{x_{i}-a_{i}}{b_{i}-a_{i}},$ (2)

where $(a_{i},b_{i})$ are the minimum and maximum requirements of flow $i$
respectively. Note that when the sending rate of flow $i$ is within its
minimum and maximum requirements (i.e., $x_{i}\in[a_{i},b_{i}]$), its
normalized rate is within $0$ and $1$ (i.e., $\overline{x_{i}}\in[0,1]$).

Figure 3: Different requirement penalties as functions of normalized rates,
for different values of D. Normalized rates which correspond to the minimum
and maximum requirements are denoted in red dashed lines.

Next, HRF is defined as the lexicographical max min vector of the normalized
rates, ordered from low to high (i.e.,
$\langle\overline{x_{1}},...,\overline{x_{n}}\rangle$ where
$\overline{x_{i-1}}\leq\overline{x_{i}}$ for every $i$). Note that the
normalized rates, used in the vector, are scaled by the requirements, which
amplifies unsatisfied requirements of low rates flows compared to higher ones.
For example, a sending rate of $9$Mbps for a flow with requirement $(10,20)$
is considered much more “critical” than a sending rate of $99$Mbps for a flow
with requirement $(100,200)$.

Therefore, HRF guarantees requirements satisfaction when possible and also
minimum unsatisfaction scaled by requirements. For example, for the $3$ flows
in Fig. 2(c), the optimal sending rates of $\langle
x_{1},x_{2},x_{3}\rangle=\langle 20,40,60\rangle$ are obtained when the
lexicographical max min of the normalized sending rates
$\langle\overline{x_{1}},\overline{x_{2}},\overline{x_{3}}\rangle=\langle
0,0,0\rangle$ is obtained.

###  III-B Hercules Utility Function

Hercules utility function shares the same congestion penalties of Proteus
scavengers utility function, including loss, RTT gradient and deviation.
However, in order to converge to HRF Hercules utility function also includes a
” _requirement penalty_ “, $H(\overline{x_{i}})$, which is a function of the
normalized sending rate.

The requirement penalty is used to factor all the congestion penalties. We
scale it from zero to one by the $\arctan$ function, which is also used as
activation function in neural networks [38]. The requirement penalty of flow
$i$, $H(\overline{x_{i}})$, is defined as follows:

$\displaystyle H(\overline{x_{i}})$
$\displaystyle=\frac{\arctan(D\cdot(\overline{x}_{i}-\frac{1}{2}))}{\pi}+\frac{1}{2}\in(0,1),$
(3)

where $D\geq 1$ is a coefficient which expresses the penalty magnitude for
rates below or above their required interval $(a_{i},b_{i})$.

Fig. 3 demonstrates different requirement penalties as functions of normalized
rates, for different values of $D$. Rates within the requirement interval
correspond to normalized rates within the interval $[0,1]$ which is denoted in
red dashed lines. We can see that the higher the $D$, the higher the penalty
for flows exceeding their maximum requirement and the lower the penalty for
flows below their minimum requirement. However, too high value of $D$ makes
the penalty function sharper and numerically closer to a step function which
can affect convergence. Instability of high values of $D$, is demonstrated in
Section V-B. In most of our experiments we used $D=2$ which obtained superior
results.

Finally, Hercules utility function is defined as follows:

$\displaystyle U(x_{i})=$ $\displaystyle(x_{i})^{t}-x_{i}\cdot
H(\overline{x_{i}})\cdot[\beta\cdot L_{i}-\gamma\cdot
max\\{0,\frac{d(RTT_{i})}{dt}\\}$
$\displaystyle-\varphi\cdot\sigma(RTT_{i})],$ (4)

where $L_{i}$ is the loss experience by flow $i$, $t=0.9$, $\beta=11.35$,
$\gamma=25$ and $\varphi=750$. Note that when no latency is experienced, the
utility function is much simpler: $U(x_{i})=(x_{i})^{t}$. Table I summarizes
Hercules notations.

In [39] we prove Theorem III.1 which states that if all senders use the
Hercules utility function and converge to equilibrium their sending rates will
be HRF.

###### Theorem III.1

In a network with $n$ flows competing over a bottleneck, where the flows are
regulated by Hercules per flow utility function (III-B) with per flow
requirements $\\{(a_{i},b_{i})\\}_{i\in[n]}$, any equilibrium is HRF.

The proof, detailed in [39], starts by showing that from some point of time a
congestion will occur. Then it follows by showing that when there is a
congestion, unsatisfied flows with low requirements have higher utility
gradient than satisfied flows with higher requirements. The proof concludes by
showing that there is no equilibrium in which low requirements flow can
increase its rate on the expanse of high requirements flow.

###  III-C Hercules Rate-Control Module

Following the online learning approach suggested by PCC [13], Hercules divides
time into sequential update intervals, where at the beginning of each
interval, a flow can be in one of the following states: (1) slow-start, (2)
probing, and (3) moving. Hercules redefines the slow-start state and its
transition condition based on the flow’s requirements. For completion, the
three states are defined as follows:

Figure 4: Hercules’ extension over QUIC objects

Slow start. When a flow starts sending, the first sending rate is selected as
the minimum between a predefined rate value 222In our evaluation we set this
value to $5$ Kbps. and the flow’s minimum requirement. Next, in every time
interval, the sending rate is doubled unless the utility function decreases or
the sending rate exceeds the flow’s maximum requirement. If one of these
conditions is met, the state transitions to probing.

Probing. In the probing state the utility gradient is estimated and used to
determine whether the flow’s rate should increase or decrease. Given a current
sending rate of $x$, the gradient estimation is performed by comparing the
utilities obtained when sending $x+\delta x$ and $x-\delta x$, where $\delta
x$ is set to be a fraction (e.g., $5\%$) of $x$. Once the direction (increase
/ decrease) decision is made the state transitions to the moving state.

Moving. In the moving state the sending keeps changing at the same direction
(following the gradient the last probing decision) until the utility decreases
(which indicates a gradient direction change). Then the state transition back
to probing.

###### Theorem III.2

In a network with $n$ flows competing over a bottleneck, where the flows are
regulated by Hercules per flow utility function (III-B) with per flow
requirements $\\{(a_{i},b_{i})\\}_{i\in[n]}$, the sending rates converge to an
equilibrium.

The proof, detailed in [39], consists of showing that the Hercules utility
function is a concave game and therefore, based on Even-dar et. al. [40],
converges to a global equilibrium point.

##  IV Implementation

Hercules’ implementation extends QUICHE, a widely deployed C$++$
implementation of QUIC, which is also used in Google Chrome. As QUICHE
supports only a single QoS per connection, Hercules rate control is performed
at the connection granularity. When future QUICHE versions will allow per flow
QoS such capabilities can be introduced to Hercules as well. As illustrated
Fig. 4, Hercules rate control logic, mainly resides in two QUICHE components:
(i) congestion control object and (ii) session object.

(a) Unbounded

(b) Single unbounded

Figure 5: Worst case satisfaction ratio for the two scenarios at different
network congestion conditions

Session object holds the connection parameters. Hercules extends it to include
the minimum and maximum requirements received from the application, and sent
to the congestion control object. Moreover, Hercules adds scheduled calls once
every update interval, which triggers the congestion control object for
calculating and updating the sending rate.

Congestion control object is extended to carry out the rate control module (as
discussed in Section III-C) based on the minimum and maximum requirements
received from the session object. More specifically, once every scheduled call
from the session object, the CC object measures the RTT and loss rate (based
on the receiving ACKs), computes the current state, the utility function, and
updates the new sending rates.

(a) $95$ Mbps

(b) $120$ Mbps

(c) $135$ Mbps

Figure 6: Average throughput for all unbounded scenario at different network
congestion conditions. The red dashed line denotes the connections’
requirements.

##  V Evaluation

We evaluate Hercules by comparing its performance to other state-of-the-art CC
protocols: BBR [10], CUBIC [11] and Vivace [13] through lab and real-word
experiments with different network conditions.

The lab experiments consist of a sender and a receiver machines, connected
through a third machine which emulates different network conditions. We also
ran live experiments on the Internet in Europe and in the US. In Europe, we
use a receiver located in London and a sender located in Frankfurt. In US we
use two AWS receivers machines, located in north California and north
Virginia, and two senders machines, located in Ohio and Oregon respectively.
All the machines run Ubuntu 20.04 OS. The network capacity was changed by
running traffic control utility (the _tc_ command) on the sender side. The
receiver reported the total received bytes in every second.

The evaluation results are described next, addressing the following challenges
of CC protocols: (i) heterogeneous requirement satisfaction in the worst and
average case (ii) convergence time, and (iii) fairness with respect to other
CC protocols.

(a) $95$ Mbps

(b) $120$ Mbps

(c) $135$ Mbps

Figure 7: Loss tolerance of the $100$ Mbps requirement connection, for the
unbounded scenario.

(a) $95$ Mbps

(b) $120$ Mbps

(c) $135$ Mbps

Figure 8: Bottleneck saturation with varying buffer size, for $100$Mbps
requirement connection, in the unbounded scenario

###  V-A Satisfying Heterogeneous Requirements

Heterogeneous Settings. Following Section I, we consider co-existing
heterogeneous connections with $5$ different minimum requirements: $10$ Kbps,
$100$ Kbps, $1$ Mbps, $10$ Mbps, $100$ Mbps, where the maximum requirements
are $1.5$ times higher, allowing $50\%$ margin. With regards to the
applications generating the connections, we considered two scenarios:

  1. 1.

All the applications have unbounded sending rate (which may exceed the maximum
requirement).

  2. 2.

All the applications have bounded sending rate except one which is unbounded.

Where unbounded applications represent network services such as file downloads
and database batch processing and synchronization, and bounded applications
may consist of Zoom streaming, VoIP, IoT devices etc.

We examined bottlenecks with $20$, $40$ and $60$ms RTT. Since all bottlenecks
had similar results and due to space limit, only $20$ ms bottleneck results
are presented. Considering that the combined minimum and maximum requirements
are $111.11$ and $166.65$ Mbps respectively, we evaluated Hercules performance
at different congestion levels:

  * •

High congestion - $95$ Mbps capacity

  * •

Medium congestion - $120$ Mbps capacity

  * •

Low congestion - $135$ Mbps capacity

The sending rates for each connection are compared between Hercules to Vivace,
BBR and CUBIC, across $70$ trials, each lasted $30$ seconds. Experiments
results consist of the allocated bandwidth and the minimum requirement for
each connection, where their ratio is referred by a _”satisfaction ratio“_ ,
i.e., $\frac{X_{i}}{a_{i}}$, where $X_{i}$ is the average allocated bandwidth
of the the connection $i$ across all intervals and trials. Moreover, we
empirically analyze the guarantee of each CC protocol, by considering
satisfaction ratio across the scenarios (of all unbounded and single
unbounded), and refer to the worst case for each networking condition.

Due to space limits, we present the live experiments results in the US, where
the receiver is located in north California and the sender in Oregon. Similar
results were obtained in the other site in the US, in Europe and in the lab.

Capacity (Mbps) | CC protocols Utilization ($\%$)
---|---
|  BBR |  CUBIC |  Vivace |  Hercules
$95$ |  94.79 |  94.80 |  94.19 |  94.23
$120$ |  94.79 |  94.80 |  93.49 |  93.99
$135$ |  94.79 |  94.80 |  93.25 |  93.94
Table II: Utilization ($\%$) of the tested CC protocols for every network
capacity

(a) Same requirements

(b) Different requirements

Figure 9: Throughput of simultaneous connections.

(a) Connections with same requirements.

(b) Connections with different requirements.

Figure 10: Throughput of non simultaneous connections.

Worst-case satisfaction. In Fig. 5 we present the worst satisfaction ratio
achieved by each of the CC protocols under different network conditions, for
single unbounded and all unbounded connections scenarios. We can see that, in
all network conditions, Hercules performs much better than other protocols,
$1.5$ and $3.5$ times better in the single unbounded and all unbounded
respectively.

As can be seen in Fig.6, the poor performance of other CC protocols in the
all-unbounded scenario, is due to the fact that they equally share the
capacity between the connections. As a result, even under low congestion (e.g,
$135$ Mbps), each connection sending rate is $27$ Mbps, which is only $27\%$
of the required bandwidth for the $100$ Mbps connection.

Overall, Hercules’ results are close to optimal throughput, obtaining $97\%$
and $92\%$ worst case satisfaction for low and medium congestion ($135$ and
$120$ Mbps) respectively. In the high congestion ($95$Mbps capacity) case the
optimal throughput is only $85\%$ satisfaction and Hercules obtains $70\%$.

Random loss tolerance. We further measured the satisfaction of the $100$Mbps
connection when introducing random loss. Fig. 7 presents the satisfaction rate
achieved in the all unbounded scenario (similar results obtained for the
single unbounded scenario). We can see that, Hercules outperform all
protocols, especially for loss rate up to $4\%$.

Buffer size tolerance. Hercules’ requirement satisfaction robustness was also
analyzed for a wide range of buffer sizes $0.5$-$5$ BDP in different network
conditions (see Fig. 8 for the all unbounded scenario). We can see that
Hercules outperform all protocols across all the checked buffer sizes, even
with shallow buffers. The results for the single unbounded scenario were
similar.

Utilization is calculated as the total sending rate across all connections
divided by the network capacity. The median utilization values of the all
unbounded scenario (for each protocol and network condition) are summarized in
Table II. It shows that Hercules utilize the network to high degree (about
$94\%$) similar to other state-of-the-art protocols. The results for the
single unbounded scenario are similar.

Figure 11: Hercules Adaptive sending rates in network where capacity changes
every $60$ seconds between $45$, $95$, $120$ and $135$ Mbps

(a) D=$1$

(b) D=$2$

(c) D=$5$

(d) D=$10$

(e) D=$100$

(f) D=$1000$

Figure 12: Requirement penalty - D value effect over convergence.

(a) CUBIC

(b) BBR

(c) Reno

(d) Vivace

Figure 13: Fairness between Hercules and other CC protocols with simultaneous
connections under high congestion ($95$ Mbps bottleneck).

(a) CUBIC

(b) BBR

(c) Reno

(d) Vivace

Figure 14: Fairness between Hercules and other CC protocols with non
simultaneous connections under high congestion ($95$ Mbps bottleneck).

###  V-B Convergence Time

Next we examine Hercules convergence in _static tests_ \- when all connections
start together, _dynamic arrival tests_ \- when some connections join during
the test and _dynamic network tests_ \- when network conditions (capacity)
change during the test.

Static tests. In the first test (Fig. 9(a)), a $95$Mbps bottleneck is shared
by $10$ Hercules connections, each with requirement of $10$Mbps. Since in this
test all the requirements are similar, HRF corresponds to a fair-share
allocation between the connections, which is achieved within a few seconds. In
the second test (Fig.10(a)), we have the same $10$ connections (each with
$10$Mbps requirement) but also a low requirement $0.5$Mbps connection. In this
test, within a few seconds, Hercules converges to a point where all
connections are close to their requirement.

Dynamic arrival tests. Fig. 10(a) presents the Hercules’ sending rate for two
connections with a $50$Mbps requirement that compete for a $95$Mbps
bottleneck, where one of them arrives $10$ seconds after the first one. We can
see that within approximately $5$ seconds after the second connection arrive,
the sending rates converge to HRF, sharing the capacity equally. Similar
result was obtained in a second test (see Fig. 10(b)), where $10$ connections,
each with $10$Mbps requirement, start together (converge to fair-share), and
$10$ seconds later, a $0.5$Mbps connection arrives. We can see that $2$
seconds later, the sending rate of all connections are close to their
requirements, regardless of their arrival time.

Dynamic network test. We further stress Hercules stability and robustness by
examining its reaction to network changes. $5$ levels of requirement
connections (from $10$Kbps to $100$Mbps) are considered, where the network
capacity changes every $60$ seconds. In addition to the capacity levels that
were analyzed so far ($95$ Mbps, $120$ Mbps and $135$ Mbps), we also
considered $45$Mbps (very high congestion). The results, presented in Fig. 11,
demonstrate that sending rates converge quickly, within a few seconds after
each capacity change.

Dynamic network test with different $D$ values. We repeat the previous dynamic
network test in order to evaluate the impact of the parameter $D$ in Hercules
utility function (Equation (3)) on the convergence, following the analytical
analysis in Section III-B. Fig. 12 presents the convergence time plots for
different parameter values ($D\in\\{1,2,5,10,15,100,1000\\}$). We can see that
for $D=1$ the initial convergence is slower compared to higher $D$ values.
Moreover, as expected, extremely high values ($D=100$ or $D=1000$) decrease
Hercules’ stability.

###  V-C Fairness with Other Protocols

We evaluate the fairness of Hercules connections towards other CC protocols:
CUBIC, BBR, Reno and Vivace. The evaluation considered two Hercules
connections, with $100$ Mbps and $5$ Mbps requirements, and a single
connection of one of the other CC protocols, with requirement of $100$ Mbps,
all sharing a $95$ Mbps bottleneck.

First, a static case is considered, where all the connections arrive to the
network simultaneously. Fig.13 presents the sending rates over time for each
connection by different CC protocols. It is shown that connections with same
requirements converge to similar sending rates regardless of protocol
(Hercules or other).

Next, we considered a dynamic scenario where the low rate connection arrives
$10$ seconds later. We can see in Fig. 14 that the final convergence outcome
and duration of all connections is similar to the static case.

##  VI Related work

Traditional CC protocols over the Internet focus on fair-share between all the
senders [13, 10, 11, 41, 42, 43]. Recently, the need to address heterogeneous
senders’ requirements motivates further studies to suggest new CC protocols.
Most of these studies consider only two flow prioritization classes: primary
and background traffic. TCP CUBIC [11] was recommended for primary flows while
Low Extra Delay Background Transport (LEDBAT) [16, 23] was used by the
background flows [17, 44]. However, according to this approach, the flows
should be prioritized in advanced, before entering the network. More flexible
approach prioritizes flows according to a threshold [18]. As a result, this
(binary) prioritization can be changed over time. Another approach suggested
to operate $4$ specific CC protocols in parallel in order to form $4$
priorities (requirement levels) [14]. However, this approach was designed for
specific use-case of video streaming, where multiple sub-flows of a single
connection require several priorities.

Meanwhile, more generalized CC protocols have been suggested, motivated by
economic model [20, 21, 22]. Each connection has its own ”share“, so in case
of congestion, the bandwidth allocation is determined based on the relative
share of each connection. However, this approach does not directly relate to
application requirements.

##  VII Conclusion and Further Research

In this work discussed and defined the desired fairness between heterogeneous
flows (named HRF). Then, we presented a new and provable CC protocol named
”Hercules“, which considers heterogeneous sender’s requirements for achieving
HRF approximation. We found that Hercules outperformed the state-of-the-art
protocols by providing higher satisfaction rate across all scenarios and
network conditions. Hercules evaluation shows its fast convergence, adaptive
to dynamic changes in the network and arrival times of flows. Moreover, we
demonstrated Hercules robustness under random loss and shallow buffers and its
fairness toward other CC protocols.

Hercules interface receives flow requirements explicitly from the
applications. A natural extension to this work can be to use new and existing
ways for classifying flows and inferring requirements based on the traffic and
the application which generates it.

## References

  * [1] L. HUAWEI TECHNOLOGIES CO., “Communications network 2030,” 2021.
  * [2] E. O’Connell, D. Moore, and T. Newe, “Challenges associated with implementing 5g in manufacturing,” _Telecom_ , vol. 1, pp. 48–67, 06 2020.
  * [3] L. Xu, “Context aware traffic identification kit (trick) for network selection in future hetnets/5g networks,” 05 2017, pp. 1–5.
  * [4] V. Jordán, H. Galperin, W. Peres, and M. Hilbert, “Fast-tracking the digital revolution: Broadband for latin america and the caribbean,” 02 2023.
  * [5] LATENCETECH, “Industrial use cases requiring 5G ultra-low latency,” 2019. [Online]. Available: https://latencetech.com/2021/07/26/blog-industrial-use-cases-requiring-5g-ultra-low-latency/
  * [6] M. M. L. Banduka, “Remote monitoring and control of industrial robot based on android device and wi-fi communication,” _Automatika: Journal for Control, Measurement, Electronics, Computing and Communications_ , vol. 56, pp. 281–291, 2015.
  * [7] M. Patel and J. Wang, “Applications, challenges, and prospective in emerging body area networking technologies,” _IEEE Wireless Communications_ , vol. 17, no. 1, pp. 80–88, 2010.
  * [8] C. Weinschenk, “Report: 5g upload speeds face challenges, phone does the heavy lifting,” Nov 202, https://www.telecompetitor.com/report-5g-upload-speeds-face-challenges-phone-does-the-heavy-lifting/.
  * [9] S. Khan, A. Hussain, S. Nazir, F. Khan, A. Oad, and M. D. Alshehri, “Efficient and reliable hybrid deep learning-enabled model for congestion control in 5g/6g networks,” _Computer Communications_ , vol. 182, pp. 31–40, 2022. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0140366421004217
  * [10] N. Cardwell, Y. Cheng, C. S. Gunn, S. H. Yeganeh, and V. Jacobson, “Bbr: Congestion-based congestion control,” _Queue_ , vol. 14, no. 5, pp. 50:20–50:53, Oct. 2016.
  * [11] S. Ha, I. Rhee, and L. Xu, “Cubic: A new tcp-friendly high-speed tcp variant,” _SIGOPS Oper. Syst. Rev._ , vol. 42, no. 5, pp. 64–74, Jul. 2008\.
  * [12] 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)_ , 2015, pp. 395–408.
  * [13] M. Dong, T. Meng, D. Zarchy, E. Arslan, Y. Gilad, B. Godfrey, and M. Schapira, “Vivace: Online-learning congestion control,” in _15th USENIX Symposium on NSDI 18_ , 2018.
  * [14] N. Rozen-Schiff, A. Navon, L. Bruckman, and I. Pechtalt, “Prism based transport: How networks can boost qos for advanced video services?” in _Proceedings of the Workshop on Design, Deployment, and Evaluation of Network-Assisted Video Streaming_ , ser. VisNEXT’21, 2021, p. 1–7. [Online]. Available: https://doi.org/10.1145/3488662.3493826
  * [15] R. Ware, M. K. Mukerjee, S. Seshan, and J. Sherry, “Beyond jain’s fairness index: Setting the bar for the deployment of congestion control algorithms,” in _Proceedings of the 18th ACM Workshop on Hot Topics in Networks_ , ser. HotNets ’19. Association for Computing Machinery, 2019, p. 17–24. [Online]. Available: https://doi.org/10.1145/3365609.3365855
  * [16] S. Shalunov, G. Hazel, J. Iyengar, and M. Kühlewind, “Low Extra Delay Background Transport (LEDBAT),” RFC 6817, Dec. 2012. [Online]. Available: https://rfc-editor.org/rfc/rfc6817.txt
  * [17] M. Geist and B. Jaeger, “Overview of tcp congestion control algorithms,” in _Network Architectures and Services_ , May 2019.
  * [18] T. Meng, N.-R. Schiff, P. B. Godfrey, and M. Schapira, “Pcc proteus: Scavenger transport and beyond,” ser. SIGCOMM ’20. Association for Computing Machinery, 2020, p. 615–631. [Online]. Available: https://doi.org/10.1145/3387514.3405891
  * [19] R. Poorzare and A. C. Augé, “Fb-tcp: A 5g mmwave friendly tcp for urban deployments,” _IEEE Access_ , vol. 9, pp. 82 812–82 832, 2021.
  * [20] L. Brown, G. Ananthanarayanan, E. Katz-Bassett, A. Krishnamurthy, S. Ratnasamy, M. Schapira, and S. Shenker, “On the future of congestion control for the public internet,” in _Proceedings of the 19th ACM Workshop on Hot Topics in Networks_ , ser. HotNets ’20. Association for Computing Machinery, 2020, p. 30–37. [Online]. Available: https://doi.org/10.1145/3422604.3425939
  * [21] L. Popa, G. Kumar, M. Chowdhury, A. Krishnamurthy, S. Ratnasamy, and I. Stoica, “Faircloud: Sharing the network in cloud computing,” _SIGCOMM Comput. Commun. Rev._ , vol. 42, no. 4, p. 187–198, Aug. 2012. [Online]. Available: https://doi.org/10.1145/2377677.2377717
  * [22] B. Briscoe, “Flow rate fairness: Dismantling a religion,” _SIGCOMM Comput. Commun. Rev._ , vol. 37, no. 2, p. 63–74, mar 2007. [Online]. Available: https://doi.org/10.1145/1232919.1232926
  * [23] O. N. Ertugay, D. Havey, and P. Balasubramanian, “Ledbat++: Congestion control for background traffic,” 2020.
  * [24] L. Yu, J. Sonchack, and V. Liu, “Cebinae: Scalable in-network fairness augmentation,” in _Proceedings of the ACM SIGCOMM 2022 Conference_ , ser. SIGCOMM ’22. Association for Computing Machinery, 2022, p. 219–232. [Online]. Available: https://doi.org/10.1145/3544216.3544240
  * [25] L. Jose, S. Ibanez, M. Alizadeh, and N. McKeown, “A distributed algorithm to calculate max-min fair rates without per-flow state,” _Proc. ACM Meas. Anal. Comput. Syst._ , vol. 3, no. 2, jun 2019. [Online]. Available: https://doi.org/10.1145/3341617.3326135
  * [26] J.-Y. L. Boudec, “Rate adaptation, Congestion Control and Fairness: A Tutorial,” 2021. [Online]. Available: https://leboudec.github.io/leboudec/latex/cc/LEB3132.pdf
  * [27] E. Danna, A. Hassidim, H. Kaplan, A. Kumar, Y. Mansour, D. Raz, and M. Segalov, “Upward max-min fairness,” _J. ACM_ , vol. 64, no. 1, mar 2017. [Online]. Available: https://doi.org/10.1145/3011282
  * [28] W. Ogryczak, “Lexicographic max-min optimization for efficient and fair bandwidth allocation,” 2007.
  * [29] H. Aziz, G. Rauchecker, G. Schryen, and T. Walsh, “Algorithms for max-min share fair allocation of indivisible chores.” S. P. Singh and S. Markovitch, Eds., 2017, pp. 335–341. [Online]. Available: http://dblp.uni-trier.de/db/conf/aaai/aaai2017.html#AzizRSW17
  * [30] B. Radunovic and J. Y. L. Boudec, “A unified framework for max-min and min-max fairness with applications,” _IEEE/ACM Transactions on Networking_ , vol. 15, no. 5, pp. 1073–1083, Oct 2007.
  * [31] A. Mas-Colell, M. D. Whinston, and J. R. Green, _Microeconomic Theory_. Oxford University Press, 1995\.
  * [32] A. Mas-Colell, M. Whinston, and J. Green, _Microeconomic Theory_. Oxford University Press, 1995.
  * [33] T. Gilad, N. Rozen-Schiff, P. B. Godfrey, C. Raiciu, and M. Schapira, _MPCC: Online Learning Multipath Transport_. Association for Computing Machinery, 2020, p. 121–135. [Online]. Available: https://doi.org/10.1145/3386367.3433030
  * [34] C. Li, T. Wan, J. Han, and W. Jiang, “Towards distributed lexicographically fair resource allocation with an indivisible constraint,” _Mathematics_ , vol. 10, no. 3, 2022. [Online]. Available: https://www.mdpi.com/2227-7390/10/3/324
  * [35] E. Hazan, “Introduction to online convex optimization,” _Foundations and Trends® in Optimization_ , vol. 2, no. 3-4, pp. 157–325, 2016.
  * [36] T. Meng, C. Cai, B. Godfrey, and M. Schapira, “Toward greater scavenger congestion control deployment: Implementations and interfaces,” in _Proceedings of the Applied Networking Research Workshop_ , ser. ANRW ’21. New York, NY, USA: Association for Computing Machinery, 2021, p. 59–61. [Online]. Available: https://doi.org/10.1145/3472305.3472323
  * [37] M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent,” 2003.
  * [38] J. Lederer, “Activation functions in artificial neural networks: A systematic overview,” _ArXiv_ , vol. abs/2101.09957, 2021.
  * [39] N. Rozen-Schiff, I. Pechtalt, A. Navon, and L. Bruckman, “Hercules: Heterogeneous requirements congestion control protocol - equilibrium analysis,” Jan. 2024. [Online]. Available: https://www.dropbox.com/scl/fi/avi10tppukdblkvdhousk/Hercules_CC_proofs.pdf?rlkey=kmwvsuz39laio9gcpkukvkl7d&dl=0
  * [40] E. Even-dar, Y. Mansour, and U. Nadav, “On the convergence of regret minimization dynamics in concave games,” in _Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing_ , ser. STOC ’09. Association for Computing Machinery, 2009, p. 523–532. [Online]. Available: https://doi.org/10.1145/1536414.1536486
  * [41] V. Arun and H. Balakrishnan, “Copa: Practical delay-based congestion control for the internet,” in _15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18)_ , 2018, pp. 329–342.
  * [42] Y. Cao, M. Xu, and X. Fu, “Delay-based congestion control for multipath tcp,” in _2012 20th IEEE International Conference on Network Protocols (ICNP)_ , Oct 2012, pp. 1–10.
  * [43] S. Floyd and T. Henderson, “The newreno modification to tcp’s fast recovery algorithm,” 1999.
  * [44] D. Havey, “Windows transport converges on two congestion providers: Cubic and ledbat,” Feb 2019, https://techcommunity.microsoft.com/t5/networking-blog/windows-transport-converges-on-two-congestion-providers-cubic/ba-p/339819.