# SMaRTT-REPS: Sender-based Marked Rapidly-adapting Trimmed & Timed Transport
with Recycled Entropies

Tommaso Bonato  Department of Computer Science, ETH Zurich  Microsoft
Corporation  Abdul Kabbani  Microsoft Corporation  Daniele De Sensi
Department of Computer Science, Sapienza University of Rome  Rong Pan
Advanced Micro Devices (AMD)  Yanfang Le  Advanced Micro Devices (AMD)
Timo Schneider  Department of Computer Science, ETH Zurich  Nils Blach
Department of Computer Science, ETH Zurich  Daniel Alves  Microsoft
Corporation  Michael Papamichael  Microsoft Corporation
Adrian Caulfield  Microsoft Corporation  Torsten Hoefler  Department of
Computer Science, ETH Zurich  Microsoft Corporation

###### Abstract

With the steady increase of machine learning (ML) workloads in datacenters,
existing congestion control algorithms fall short of delivering the required
performance at scale. ML traffic is bursty and bulk-synchronous and thus
requires quick reaction and fairness. We show that existing CC algorithms that
use delay as a main signal react too late and are not always fair. We design
SMaRTT, a simple sender-based congestion control algorithm that uses both RTT
and ECN as congestion signals and, if supported by network switches, packet
trimming in order to react quickly. SMaRTT introduces the new concept of
QuickAdapt which estimates the bandwidth available at the receiver based on
congestion signals. We couple SMaRTT with a new per-packet traffic load-
balancing algorithm that we call REPS, which effectively reroutes packets
around congested hotspots and flaky or failing links. Our evaluation shows
that SMaRTT improves performance by up to 38% and 33% over EQDS and a Swift-
like algorithm, respectively.

##  1 Introduction

In the quickly-evolving landscape of AI-centric datacenters, the demand for
large-scale and high-performance computing capabilities has risen to
unprecedented heights. This paradigm shift is demonstrated by the exponential
growth of large-scale AI training [thompson2022computational, oaiscale] and
the proliferation of high-performance computing (HPC) offerings in the cloud
[cloudnoise]. On these workloads, the demand for high throughput at an
affordable cost and low latency has become extremely important, and a crucial
component to achieving those targets lies in network infrastructure and
protocols.

A notable manifestation of this demand is found in the statistics - a
staggering 70% of Azure’s traffic is now carried by Remote Direct Memory
Access (RDMA) technology [286500], and all the major cloud providers are
investing in similar technologies [9167399, 278358, cloudnoise]. Yet, as we
witness this transformation, it is worth acknowledging that existing
networking protocols may not suit the demands of high-bandwidth networking at
scale. For example, lossless RDMA over Converged Ethernet (RoCE) is affected
by several issues like the excessive switch buffer requirements for Priority
Flow Control (PFC), PFC storms, and in-order delivery assumptions [10154243,
10.1145/3230543.3230557].

To address many of these shortcomings, we introduce a new congestion control
algorithm which we call SMaRTT (Sender-based Marked Rapidly-adapting Trimmed &
Timed Transport), together with the novel REPS (Recycled Entropy Packet
Spraying) load balancing scheme. SMaRTT-REPS runs over lossy Ethernet networks
and addresses the challenges posed by new workloads and technology evolution
by achieving reactiveness, visibility, and deployability as we explain in the
following.

Figure 1: Comparison of SMaRTT with EQDS and a Swift-like protocol all using
REPS.

##### Reactiveness

Modern datacenter traffic can consist of a series of frequent but small
requests by RPC-like protocols. For example, 80% of RPCs in Google datacenters
fit in 1 bandwidth-delay product (BDP), and 89% fit in 4 BDP [286425]. This
behavior is also present in some AI workloads where nodes need to frequently
exchange a few KiB of data [10.5555/3571885.3571899]. The bursty nature of
such traffic [10.1145/3131365.3131375] poses significant challenges for the
congestion control algorithm. Algorithms relying on delay as congestion signal
often react too late to such transient bursts [286425,
10.1145/3131365.3131375], leading to an increase in flow completion time and a
decrease in fairness. Moreover, algorithms that do not start sending
immediately at full line rate will also suffer in such scenarios.

This is shown in the left part of Fig. 1, where we report the Cumulative
Distribution Function (CDF) of the Flow Completion Time (FCT) of 1MiB flows in
a permutation scenario with 1,024 nodes (more details in Section 4). We
compare receiver-driven congestion control algorithm (EQDS [278348]), with a
sender-driven, delay-based one similar to Swift [49448] extended with packet
spraying and trimming support. We also show the FCT for SMaRTT, that instead
relies on a combination of ECN and delay to react to congestion.

Fast-reacting algorithms that can minimize jitter and keep FCT low and
consistent are particularly important in the context of AI and HPC workloads
that exhibit tightly coordinated and synchronized communication patterns. In
such systems, performance is often dictated by the slowest node in the system
[netnoise1, netnoise2, tailatscale] as ”straggler” flows and growing
variability in completion times can have a disproportionately high impact on
overall job progress.

##### Visibility

Many congestion control algorithms (especially receiver-based ones) have been
optimized for managing congestion at the final hop caused by incast
[10.1145/3098822.3098825, 278348], due to its relevance for traditional TCP
traffic [10.1145/1592681.1592693]. However, with the emergence of new
transport protocols and workloads, those algorithms provide sub-optimal
performance, since they might have limited visibility of congestion happening
in the network fabric. This type of congestion is often the result of
oversubscription (traffic exceeding the capacity of the network), e.g., common
at upper tiers of datacenter networks [286425, 278358], but can also occur in
a non-oversubscribed setting as a result of ECMP [conga, drill,
10.1145/2535372.2535375] collisions that can form hot spots depending on how
flows are hashed across available paths. This is shown in the right part of
Fig. 1, where we can see that EQDS performs poorly due to its inability to
adapt to fabric congestion, hence wasting bandwidth due to trimmed packets and
re-transmissions. As we show in Sec. LABEL:sec:todo, this could be improved by
completing EQDS with sender based congestion control protocols.

##### Deployability

The constant increase in the number of nodes used by workloads and in the
number of network flows per node [10.1145/2829988.2787472] limits the amount
of memory that can be used to keep track of flow state. This is even more
critical when we consider that network bandwidth is rapidly reaching the
Tbit/s range and that, for performance reasons, (part of) the congestion
control algorithm would be implemented in Network Interface Cards (NICs).

This limits the amount of memory the algorithm can use and the complexity of
the algorithms that can be executed (at 800Gbit/s, with 4KiB packets, the NIC
needs to process one packet every 40 nanoseconds). Similarly, the increasing
bandwidth that network switches need to manage (51.2 Tbit/s and higher at the
time of writing) limits the complexity of features that those switches can
implement. Congestion control algorithms relying on specific (new) features to
be supported by the hardware [10.1145/3341302.3342085,
10.1145/3386367.3431316, 276958] limit their use in datacenters, where new
generations of switches are incrementally deployed.

###  1.1 Contributions

To address the aforementioned challenges, in this paper we introduce the
following key contributions:

##### SMaRTT

A simple yet highly responsive and very stable sender-based congestion control
mechanism that does not rely on any advanced in-band network telemetry (INT).
It instead leverages a combination of ECN-marking and round-trip-time (RTT)
measurements, two signals that have been commonly used in a mutually exclusive
manner despite each of them possessing distinctive valuable benefits that
complement one another (as we show in Sec. 3.1). Moreover, SMaRTT efficiently
uses resources, since it only needs to store a few bytes per flow and does not
require any pull queue or specific packet types, as common in many receiver-
driven algorithms. SMaRTT shows how packet trimming is ideal for handling
packet drops in congested scenarios. It has been shown that packet trimming
can be easily implemented on many existing switches such as Broadcom Trident 4
and NVidia Spectrum 2 by exploiting their deflect-on-drop (DoD) capabilities
[adrian2022implementing]. Yet, SMaRTT also proposes a viable alternative in
case where trimming is not supported, with a limited performance hit. SMaRTT
performance is very close to the ideal one in most cases and it is able to
improve reactiness over Swift-like algorithms and also more general than
existing receiver-based algorithms.

##### REPS

An ultra lightweight yet very powerful adaptive load balancing mechanism which
we call Recycled Entropy Packet Spraying (REPS, Sec. 3.7). REPS can sustain
near-optimal performance at high bandwidth utilization levels and can very
effectively route around path blackholes. Differently from complex in-network
load balancing implementations [10.1145/3295500.3356196, 9825915], REPS does
not require any switch support. We demonstrate how congestion control and
adaptive load balancing can be efficiently orchestrated. By doing so, on one
side the congestion control does not inhibit early yet mild congestion signals
crucial for load balancing adaptivity. On the other side, load balancing does
not aggressively shift substantial portions of traffic away to different
paths, which could make the received congestion signals too irrelevant.

##### Sender-based Packet Trimming

We extend the scope of emerging switch-based packet trimming support to
encompass sending-based congestion control schemes. If packet trimming is not
available, SMaRTT falls back to a timeout-based mechanism (Sec. 3.3) and we
show how, by setting an aggressive timeout and integrating other features of
SMaRTT it is possible to only incur a minor additional delay when using
timeouts.

##### QuickAdapt

We introduce QuickAdapt (Sec. 3.3), an accurate technique for quickly
converging to the achievable bandwidth capacity at any bottleneck, typically
within one RTT of receiving a serious congestion signal such as a trimmed
packet or a timeout. The technique copes very well with the aforementioned
packet trimming feature during incast episodes, for example, but it has been
generalized to promptly and efficiently address any severe congestion events.
We demonstrate how QuickAdapt can be leveraged to enable safe yet rapid packet
loss recovery (essentially down to the best one can achieve with an out-of-
order packet delivery transport that has no access to explicit packet loss
signaling). We also argue that this feature can be retrofitted to any
transport mechanism operating within tight RTT bounds, thus significantly
reducing tail latencies.

##### Fair Increase/Decrease

We introduce a new congestion window reduction technique (called Fair
Increase/Decrease) to help achieve better bandwidth fairness (Sec. 3.2.1 and
Sec. 3.2.3). We also introduce a new mechanism to that can rapidly increase
the congestion window of flows (Sec. 3.4) if no congestion is detected for a
period of time, thus minimizing any small degree of unfairness that might have
developed.

##  2 Related Work

Congestion control in datacenter networks has a long history. We categorize
below the different congestion control mechanisms according to the congestion
signal they use, and to how they control the transmission rate.

###  2.1 Congestion Control Signals

The choice of the signal to use to detect congestion largely impacts the
reactiveness of the algorithm.

##### Delay-based

The simplest signal is time, where either the sender measures the round trip
time (e.g., in Swift [49448] and TCP [1092259]) or the receiver annotates
acknowledgment packets (ACK) packets with one-way delay information (e.g.,
TIMELY [43840] or DX [7544640]). How to accurately measure time is critical
and can require special OS or hardware support such as Snap in Swift [49448].
Time-based signals are often described as “multi-bit” as they account for the
exact queuing delay along the path in the network.

##### Explicit Congration Notification (ECN)

ECN is in widespread use today in datacenters and is available in all modern
switches. Algorithms like DCTCP [10.1145/1851182.1851192], Hull [180607], and
D2TCP [10.1145/2342356.2342388] all rely on ECN marking. For example, DCQCN
[zhu2015congestion] combines ECN and Priority-based Flow Control (PFC) to
quickly react to congestion. However, although ECN-based algorithms can react
quicker than time-based ones, they perform poorly when dealing with incast and
can be challenging to tune [49448]. With SMaRTT, we combine the best of the
two signals, by combining delay and ECN signals to promptly react to
congestion.

##### In-Network Telemetry

While ECN is a very simple widely available example for in-network telemetry
(INT), other protocols rely on more complex signaling such as maximum queue
occupancy along the path. Modern switches offer a plethora of such signals and
protocols using those are in active development. HPCC
[10.1145/3341302.3342085], for example, uses precise load information along
the path to adjust its rate at the sender.

###  2.2 Rate Control

The decision on how to react to congestion can occur in different parts of the
network, and this has a direct impact on the visibility and on which type of
congestion the algorithm can react to.

##### Receiver-based

Some algorithms exploit the knowledge of the receiver about concurrently
incoming flows to schedule the transmission by the different senders directly.
Many of these schemes such as NDP [10.1145/3098822.3098825], EQDS [278348],
pHost [10.1145/2716281.2836086], ExpressPass [9047463], SMSRP
[10.1145/2807591.2807600], and Homa [10.1145/3230543.3230564] maintain end-to-
end credits that are used to adjust sender flow rates. However, whereas these
schemes can deal very well with incast traffic, they usually fall short when
dealing with congestion happening in other parts of the network [49448].

##### Sender-based

In algorithms like Swift [49448], DCQCN [zhu2015congestion], DCTCP
[10.1145/1851275.1851192] and others, it is instead the sender that decides
how to adjust its transmission rate (after receiving congestion information
back from the receiver). In some schemes like PACC [9796803], switches can
directly indicate congestion back to the sender and thus shortcut the path to
the receiver.

##### Switch-based

In some algorithms such as RoCC [10.1145/3386367.3431316] and BFC [276958] the
switches directly assign rates to sources. However, these solutions are hard
to deploy since they require the switch to support some features (and/or to be
programmable). Moreover, the limited amount of hardware resources available in
the switch requires a complex design and it is unclear how those solutions
would scale when increasing the number of flows and / or endpoints in the
network.

##  3 SMaRTT Design

Our main goal with SMaRTT is to create a low-resource and easy-to-deploy
congestion control algorithm that works with existing contemporary switches,
but that coud also take advantage of next-generation switches supporting
packet trimming. We design SMaRTT such that it can quickly react to congestion
happening both at the last hop (incast) as well as in any other part of the
network. We also do not make any particular assumption on the type of traffic
that shall be supported by it.

In this work we mainly focus on widely used fat tree networks [51587,
cloudnoise]. However, SMaRTT could be easily adapted to work with other
topologies such as Dragonfly [4556717, 278358, 9355230], BCube
[10.1145/1592568.1592577], SlimFly [10.1109/SC.2014.34], HxMesh
[10.5555/3571885.3571899] and others. Similarly to EQDS [278348], we assume
that each switch port has a high-priority queue used to forward headers
(trimmed packets and ACK packets), and a lower-priority queue to forward data
packets. By doing so, packets carrying potential congestion information are
prioritized so that SMaRTT can react quickly.

We intentionally limit buffering to a worst-case scenario, assuming that each
per-port queue is one bandwidth-delay product (BDP) in size. Last, all nodes
know the base RTT (i.e., the RTT on an empty network). Because it depends on
the number of hops between two nodes, each node stores the base RTT for any
hop count (we have a limited number of possible hop counts since we are
considering fat trees). This can either be computed and stored statically when
the network is setup, or adjusted dynamically similarly to what done by Swift
[49448].

###  3.1 SMaRTT Congestion Signals

Choosing the congestion signal is critical for the whole design of the
protocol, and SMaRTT uses both ECN and delay (RTT). ECN marking is supported
by all modern switches used in datacenters, whereas NIC timestamping for
accurate delay computation can be implemented in the NIC [49448, 286500].
Although ECN was originally designed to mark packets when they are enqueued
[rfc3168], it has been shown that marking packets when they are dequeued
improves reactiveness to congestion and can be easily implemented on most
existing switches [wu2012tuning]. For these reasons, in the rest of the paper,
we assume that switches mark ECN packets when they are dequeued.

In Fig. 2 we compare ECN and delay as congestion signals, by simulating 16:1
incast traffic. We use the same congestion control logic in both cases
(decreasing at most by half a MTU per packet in response to high delay or ECN
marking) and network conditions but different congestion signals. We use
blocking fat trees with 1024 nodes and link speed of 800Gbps (more details in
Section 4).

We observe that both the individual per-packet RTT and the queue sizes
decrease much faster when using ECN. The reason is that ECN marks the packet
at the front of the queue, allowing the congestion signal to arrive earlier to
the sender, which can then react accordingly. On the other hand, when using
delay as the congestion signal, the receiver gets the congestion signal only
after the packet crosses the entire queue. This difference is also present
when increasing the network bandwidth since, even if the transmission time of
each packet is reduced, switch buffers are larger thus increasing queueing
time.

Figure 2: Comparing ECN and delay-based congestion signals during an incast.

Delay can act as a more precise and fine-grain congestion signal due to its
multi-bit nature (differently from the single bit of traditional ECN). Delay
estimates congestion more accurately and allows the algorithm to also be more
fair since it does not introduce the extra randomness inherently present with
ECN. We show this in Fig. 3, where we report the distribution of FCTs of the
previous experiment. We can see that, even if the average FCT is smaller for
ECN, the maximum FCT is larger, and this would delay tightly coupled
applications such as ML training workloads.

Figure 3: Comparing ECN and delay-based congestion signals during an incast.

Finally, it is important to determine how often to react to congestion
signals, especially when decreasing the congestion windows. Many algorithms
such as Swift or DCQCN react once per period of time (e.g., once per RTT). As
shown in Fig. 4, however, reacting on a per-packet basis results in better
performance, as it improves reactiveness and eliminates any possible
unfairness caused by a single decrease over a period of time. As shown in the
figure, having a per-packet reaction improves fairness as well as average FCT.

Figure 4: Comparing per-packet and per-RTT congestion signals during a
permutation.

###  3.2 Main Control Loop

Every time the sender receives an ACK, it might resize its congestion window
(cwnd, determining the maximum number of in-flight packets) to achieve a pre-
determined and constant target RTT. As we will explain in Sec. 3.6, we assume
the target RTT to be 1.5x higher than base RTT. When an ACK is received, four
different scenarios can occur depending on the severity of congestion (or lack
thereof): Fair Decrease, Multiplicative Decrease, Fair Increase,
Multiplicative increase.

####  3.2.1 Fair Decrease (FD)

The ACK is ECN-marked but the reported RTT is smaller than the target one. In
this case, queues are starting to build up but the current packet has not been
significantly affected yet and the RTT signal can’t be considered accurately,
hence SMaRTT reacts by gently decreasing the window regardless of the RTT of
the packet. To improve fairness (see Sec. 4.3), the congestion window is
decreased more aggressively for flows with larger windows (and thus, most
likely, more in-flight bytes) as follows:

$\displaystyle cwnd\mathrel{-}=\frac{cwnd}{bdp}\cdot fd\cdot p.size$

where $bdp$ is the bandwidth-delay product (computed considering the base
RTT), $fd$ is fair decrease constant, and $p.size$ is the size of the
acknowledged packet. Intuitively, the higher $fd$, the higher the reduction
for flows with larger congestion windows. We discuss how to choose $fd$ in
Sec. 3.6.

####  3.2.2 Multiplicative Decrease (MD)

The ACK is ECN-marked and reports an RTT higher than the target one. This is
an indication of a worst-case scenario where the most up-to-date signal (ECN)
reports there are many enqueued packets in the network. Moreover, the packet
itself also experienced high queueing delay (high RTT). As a consequence,
SMaRTT rapidly reduces the congestion window by applying a multiplicative
decrease as follows:

$\displaystyle cwnd\mathrel{-}=min\Big{(}size,\frac{p.rtt-trtt}{p.rtt}\cdot
md\cdot p.size\Big{)}$

Where $trtt$ and $p.rtt$ are the target RTT and the measured RTT respectively.
By applying the multiplicative decrease SMaRTT decreases the congestion window
proportionally to the distance between the target and measured RTT. To improve
fairness, SMaRTT additionally applies the Fair Decrease described before. In
any case, $cwnd$ is decreased by at most by the size of the acknowledged
packet.

$md$ is a multiplicative decrease constant depending on the target RTT. Its
value is selected so that when the RTT is twice the target RTT, the congestion
window is decreased by a packet for each ACK. Thus, we want to have
$\frac{p.rtt-trtt}{p.rtt}\cdot md\cdot p.size=p.size$, which implies $md=2$.

####  3.2.3 Fair Increase (FI)

The ACK is not ECN-marked but reports an RTT higher than the target one. This
might indicate that the congestion signal from the RTT is outdated and there
is no significant queue build-up happening. As a consequence, SMaRTT gently
increases the congestion window discarding the RTT signal. To improve fairness
(see Sec. 4.3), the window is increased more aggressively for flows with
smaller windows as follows:

$\displaystyle cwnd\mathrel{+}=\frac{p.size}{cwnd}\cdot mtu\cdot fi$

where $fi$ is a fair increase constant and $mtu$ is the Maximum Transmission
Unit. Intuitively, the higher $fi$, the higher the reduction for flows with
larger congestion windows. We discuss how to choose $fi$ in Sec. 3.6.

####  3.2.4 Multiplicative Increase (MI)

The received ACK is not ECN-marked and reports an RTT smaller than the target
one. In this case, SMaRTT significantly increases the congestion window by
doing a multiplicative increase as follows as there are no indications of
congestion happening:

$\displaystyle
cwnd\mathrel{+}=min\Big{(}size,\frac{trtt-p.rtt}{p.rtt}\cdot\frac{p.size}{cwnd}\cdot
mtu\cdot mi\Big{)}$

By doing so SMaRTT increases the congestion window less aggressively the
closer the RTT is to the target RTT. To improve fairness, this is followed by
the gentle increase described before.

$mi$ is a multiplicative increase constant depending on the network bandwidth
and target RTT. $mi$ must be selected so as to increase the congestion window
by at most half an MTU per RTT. If we assume $cwnd/p.size$ ACKs are received
in an RTT, the window would be increased by $\frac{trtt-p.rtt}{p.rtt}\cdot
mtu\cdot mi$ per RTT. Because we want this quantity to be at most $mtu/2$, we
have $mi\leq\frac{rtt}{2(trtt-p.rtt)}$. Since $p.rtt>brtt$, where $brtt$ is
the base RTT, we set $mi=\frac{brtt}{2(trtt-brtt)}$.

####  3.2.5 Overall Picture

Algorithm 1 summarizes the main SMaRTT logic. It is worth remarking that,
besides the four scenarios we just presented, SMaRTT introduces some
optimizations, that we are going to describe in the following. When designing
SMaRTT, we took particular care to keep its memory footprint low to ensure
scalability and ease of hardware implementation on NICs. Table shows the per-
connection and global memory requirements of SMaRTT (some of these variables
will be presented in the next sections).

| Variable | Unit | Size [B]
---|---|---|---
Per-Conn. | cwnd | Bytes | 3
end | Nanoseconds | 4
trigger_qa | Boolean | 1
increase | Boolean | 1
bytes_ignored | Count | 2
bytes_to_ignore | Count | 2
acked | Bytes | 2
| Total | - | 15
Global | max_cwnd | Bytes | 3
brtt | Nanoseconds | 4
trtt | Nanoseconds | 4
bdp | Bytes | 3
mtu | Bytes | 2
fi | Bytes | 2
mi | Bytes | 2
fd | Bytes | 2
md | Bytes | 2
| Total | - | 24
Table 1: Per Connection and Global States of SMaRTT

###  3.3 QuickAdapt

When a packet drop is detected, the congestion window is decreased by the size
of the dropped packet, and the packet is retransmitted. By default, SMaRTT
relies on packet trimming to detect packet losses. Traditionally, when using
packet trimming, the switch removes the packet payload and forward the header
if the queue size exceeds a given threshold [10.1145/3098822.3098825]. This
allows congestion information to be communicated to the receiver even on
congested networks. With SMaRTT, we trim packets only when they would
otherwise be dropped because of a full buffer.

Although we expect next-generation switches to widely support packet trimming,
we also want SMaRTT to be compatible with switches lacking such support. If
trimming is not supported, SMaRTT falls back to a simple timeout-based
approach, requiring minimal changes to the overall SMaRTT logic and, its
overall design, allows us to set fairly aggressive timeouts. We also double
the value of the $md$ constant. This limits how aggressively the congestion
control can ramp up and reduces the probability of packet drops (which is
higher due to the lack of trimming), which can decrease performance and reduce
link efficiency. We compare SMaRTT performance with and without trimming in
Sec. 4.2.

Algorithm 1 SMaRTT Pseudocode

1:$acked,bytes\\_ignored=0$ $\triangleright$ Sec. 3.3

2:

3:procedure congestion_loop_logic(p)

4: $acked\mathrel{+}=p.size$

5: $bytes\\_ignored\mathrel{+}=p.size$

6:

7: if p.is_ack then

8: if $bytes\\_ignored<bytes\\_to\\_ignore$ then

9: return $\triangleright$ Ignore ACKs after QuickAdapt (Sec. 3.3)

10: end if

11:

12: $adp=\text{quick\\_adapt(p)}$ $\triangleright$ Sec. 3.3

13: $finc=\text{fast\\_increase(p)}$ $\triangleright$ Sec. 3.4

14: if $adp$ or $finc$ then

15: return $\triangleright$ Exit if QuickAdapt or FastIncrease triggered

16: end if

17:

18: if p.ecn and $p.rtt\leq trtt$ then

19: fair_decrease(p) $\triangleright$ Sec. 3.2.1

20: else if p.ecn and $p.rtt>trtt$ then

21: multiplicative_decrease(p) $\triangleright$ Sec. 3.2.2

22: else if !p.ecn and $p.rtt>trtt$ then

23: fair_increase(p) $\triangleright$ Sec. 3.2.3

24: else if !p.ecn and $p.rtt\leq trtt$ then

25: multiplicative_increase(p) $\triangleright$ Sec. 3.2.4

26: end if

27: else if $p.is\\_trimmed$ or $p.timeout\\_triggered$ then$\triangleright$
Sec. 3.3

28: $cwnd\mathrel{-}=p.size$

29: trigger_qa = true

30: retransmit_packet(p)

31: if $bytes\\_ignored>=bytes\\_to\\_ignore$ then

32: quick_adapt(p) $\triangleright$ Sec. 3.3

33: end if

34: end if

35: cwnd = max(min(cwnd, bdp), mtu) $\triangleright$ Sec. 3.5

36:end procedure

Whether a packet loss is detected through trimmed packets or timeouts, this is
usually an indication of heavy congestion. For this reason, SMaRTT applies a
technique that we call QuickAdapt, to converge quickly to an appropriate
congestion window size. QuickAdapt somewhat emulates what would happen in
receiver-based congestion control algorithms, by adapting our window to the
actual receiving rate of ACKs and trimmed packets but without needing any
special support on the receiver side (e.g. pull queues).

Algorithm 2 QuickAdapt Pseudocode

1:procedure quick_adapt(p)

2: adapted = false

3: if $\text{now}\geq\text{end}$ then $\triangleright$ QuickAdapt at most once
per target RTT

4: if trigger_qa and end $\neq$ 0 then

5: trigger_qa = false

6: adapted = true

7: cwnd = max(acked, mtu)$\cdot$ qa_scaling

8: bytes_to_ignore = unacked $\triangleright$ Ignore next congestion signals

9: bytes_ignored = 0

10: end if

11: end = now \+ trtt

12: acked = 0

13: end if

14: return adapted

15:end procedure

SMaRTT counts how many bytes are received over the last $trtt$ and, if a loss
is detected, it sets the congestion window to such value. It is possible to
scale that value by a constant ($qa\\_scaling$) depending on the desired queue
occupancy. For instance, in this work, since we are using target RTT to
collect how many bytes the sender gets acknowledged, we multiply it by $0.8$,
in order to drop our queue to around $K_{min}$. Keeping it to 1 would drop it
to roughly in-between $K_{min}$ and $K_{max}$, since we choose the target RTT
to be in-between them, as described in Sec 3.6.

Because the sudden change caused by QuickAdapt already takes into account the
subsequent feedback, the receiver ignores the congestion information carried
by all the unacked packets received from the moment QuickAdapt is triggered.
Doing so is important to avoid overreacting to congestion. For the same
reason, QuickAdapt is called at most once per target RTT.

The QuickAdapt pseudocode is presented in Algorithm 2, while the interaction
with the rest of the SMaRTT logic is visible in the previously presented
Algorithm 1. In Figure 7 we show a simplified example of QuickAdapt in action
with a 2:1 incast. Note that we chose artificial buffer and window sizes to
simplify the exposition.

Figure 5: QA behaviour over time for a 2:1 incast: Senders have a starting
window of 4 packets, when a sender gets a trimmed packet it sets trigger_qa to
true. Once one trtt of time has passed, it changes its sending rate to the
number of acked packets (2 in this case) during this time window. Algorithm 3
FastIncrease Pseudocode

1:procedure fast_increase(p)

2: if $rtt\approx brtt$ and not p.ecn then

3: $count\mathrel{+}=p.size$

4: if $count>cwnd$ or $increase$ then

5: $cwnd\mathrel{+}=k\cdot mtu$

6: $increase$ = true

7: return increase

8: end if

9: else

10: $count=0$

11: $increase$ = false

12: end if

13: return increase

14:end procedure

###  3.4 FastIncrease

To quickly reclaim bandwidth available after the termination of some flows
(e.g., in case of incasts with uneven sizes), SMaRTT relies on FastIncrease.
Every time an ACK is received, if the monitored RTT is close to the base RTT
and the packet is not ECN marked, the congestion window is incremented by $k$
MTUs. $k$ is a constant that we set equal to $2$ and we scale proportionally
to the network bandwidth (see Sec. 3.6). We show the FastIncrease pseudocode
in Algorithm 3, and how to interact with the rest of the SMaRTT logic in
Algorithm 1

###  3.5 Minimum and Maximum Window Size

SMaRTT enforces the congestion window size to be within some predefined range.
We currently assume a minimum window of 1 MTU. At modern link speeds and
latencies (with a BDP around 900KiB and 4KiB MTUs) this allows to easily
support high degree of incast with hundreds (200 in this example) of senders
targeting a single receiver. Even higher degrees of incast can be gracefully
handled by SMaRTT (at reduced link efficiency due to the potentially large
number of trimmed or dropped packets) but these are unlikely to show up in
modern AI workloads where traffic is well-behaved and dominated by highly
optimized collectives that limit or completely avoid incast
[10.5555/3571885.3571899]. For scenarios where communication is dominated by
high degree of incast, the pacer solution adopted by Swift for cases when the
window drops below 1 MTU [49448] would work in SMaRTT as well. SMaRTT also
enforces a maximum window size of 1 BDP.

###  3.6 Parameters Selection and Memory Requirements

We now describe how to select the SMaRTT parameters previously described.

  * •

For ECN marking, $K_{min}$ and $K_{max}$ are set to $20\%$ and $80\%$ of the
switch queue size respectively. The probability of a packet being ECN-marked
is linear in the queue size, hence implementing a RED queue [251892].

  * •

The target RTT ($trtt$) is selected to be equal to $1.5x$ the base RTT,
corresponding to half-full switch queues, so halfway in between $K_{min}$ and
$K_{max}$. By doing so, SMaRTT does not immediately kick in, allowing the REPS
load balancing to react by forwarding packets on a different path, before
taking more drastic actions involving a reduction of the congestion window.

  * •

We set the $fi$ and $fd$ parameters (see Sec. 3.2) to $0.25$ and $0.8$
respectively for a given link speed and MTU size (100Gbps and 4096B), after
running an extensive tuning suite where we evaluated hundreds of combinations
in all test scenarios of Section 4. Both these parameters are related to
fairness, and the higher they are (up to a reasonable extent), the higher they
will give advantages to flows with smaller windows.

  * •

Last, some values need to be scaled according to the network bandwidth, since
with higher bandwidth, we have a higher BDP and, thus a larger maximum
congestion window. Consequently, the congestion window can be increased more
aggressively on networks with higher bandwidth. Namely, the $fi$, $mi$, and
$k$ parameters need to be multiplied by $\gamma=\frac{bw}{100Gb/s}$, where
$bw$ is the network bandwidth (in Gbit/s). On the other hand, to be more
conservative, both $fd$ and $md$ are fixed regardless of link speed as we
always want to react strongly in case of congestion.

###  3.7 Recycled Entropy Packet Spray (REPS)

Besides the congestion control algorithm, we couple SMaRTT with a novel per-
packet load balancing mechanism which we call REPS, and which relies on ECMP
[ecmp]. With ECMP, each switch computes a hash function over some fields in
the packet header to determine on which path to forward the packet. One of
these fields is the entropy, which REPS changes on a per-packet basis. With
REPS, each connection keeps a small fixed-size cache of entropies and an
additional modular counter.

Whenever an ACK arrives, the carried entropy is added to the cache. Whenever a
new data packet is to be sent, its entropy is taken from the cache. If a data
packet finds no entropies in the cache, it increments the counter and uses the
new count as an entropy. Initially, all entropies are cycled in a round-robin
fashion to explore them all. One can easily define some additional simple
policies, e.g., make the cache a priority queue and insert entropies based on
their RTTs or ECN marking or a combination thereof, but we do not explore this
further in this work. Algorithm 4 shows the REPS pseudocode:

Algorithm 4 REPS Pseudocode

1:$num\\_entropies=256$

2:$next\\_entropy=0$

3:$cached\\_entropy=0$

4:procedure reps(p)

5: $\triangleright$ highest_sent is the highest packet sent in bytes

6: if highest_sent ¡ max$(bdp,num\\_entropies\cdot mtu)$ then

7: $next\\_entropy++\,\,\,\%\,\,\,num\\_entropies$

8: else$\triangleright$ cached_entropy is used when a new packet is sent out

9: if $p.ecn$ then

10: $cached\\_entropy=next\\_entropy++\,\,\,\%\,\,\,num\\_entropies$

11: else

12: $cached\\_entropy=p.entropy$

13: end if

14: end if

15:end procedure

We evaluate REPS’ advantages versus traditional packet spraying and ECMP in
Sec. 4.1.

##  4 Evaluation

We evaluate the performance of SMaRTT-REPS using the htsim packet-level
network simulator [10.1145/3098822.3098825]. In our experiments, we consider
two different fat tree topologies, one with 1024 and the other with 128 nodes.
We set a 4KiB MTU size and 800 Gbps network bandwidth, as it is the speed
being used for the latest generation of switches . Switch traversal and link
latency are set to 300ns and 400ns, respectively, in line with latest switch
technology [9355230].

##### State-of-the-art Comparison

We evaluate SMaRTT-REPS against EQDS and a Swift-like algorithm. It varies
slightly from Swift as we could not get access to the original constants and
also we adapted it to support both trimming and multi-pathing. We note that
EQDS has already been shown to consistently outperform both DCTCP and DCQCN
[278348]. To make the comparison fair with a focus on the congestion control
side, we use REPS for all the algorithms and all the experiments, except when
stated otherwise. We also evaluate performance on two different oversubscribed
fat trees, with 4:1 and 8:1 oversubscription ratios. We also note how such
topologies are commonly deployed in production datacenters [43837].

##### Analyzed Workloads

We consider the following three workloads: (i) incast: relevant for datacenter
workloads, that often send requests to a large number of workers, and must
then handle their near-simultaneous responses; (ii) permutation: simulates
point to point connections which is common in many workloads while also
stressing the load balancer as we force each packet to always cross the core
switches; (iii) alltoall: relevant for many AI workloads especially during
training.

In the following, we first analyze the performance gain obtained through the
use of REPS (Sec. 4.1), as well as the advantages of using packet trimming
(Sec. 4.2). Then, we compare SMaRTT performance with state-of-the-art
algorithms on incast (Sec. 4.3), permutation (Sec. 4.4), and alltoall (Sec.
4.5) workloads.

Figure 6: Flow completion times comparing REPS with oblivious packet spraying.

###  4.1 REPS Advantages

In Figure 6, we compare SMaRTT performance when using oblivious packet
spraying and when using REPS, for a 32MiB permutation workload on a 4:1
oversubscribed fat tree. We can see from the results how REPS significantly
improves fairness compared to oblivious packet spraying.

Figure 7: REPS behaviour in a scenario with one sender and one receiver with
an intermediate switch. We assume the sender is in the else branch of
Algorithm 4 (lines 8 – 14), changing the entropy whenever an ECN is received.

In particular, if we go more in detail, looking at the RTT distribution, we
can see how REPS is characterized by a lower RTT variability. Moreover,
differently from oblivious packet spraying, the RTTs are closer to the target
one, indicating a better utilization of the network. This also improves the
completion time by roughly 10% compared to oblivious spraying. Last, we also
observe that when using per flow ECMP that the job completion time is more
than twice that of packet spraying and REPS, due to more flow collisions (not
shown in the plot). However, the individual RTT of per-flow ECMP are low
because SMaRTT lowered the sending rate after detecting the congestion.

Figure 8: Violin plots showing the RTT distribution of each individual packet
comparing REPS with oblivious packet spraying and per-flow ECMP.

###  4.2 Trimming vs. Timeouts

When running workload with large messages, the impact of not having trimming
is minimal to the completion time as a relative value, since the delay by not
using trimming is constant and at most 2 base RTT.

However, when running small messages this becomes evident, as we show in Fig.
9 for 512KiB messages, where we can see how having trimming support improves
flow completion time by slightly more than 1 base RTT (equal to 8.6 $\mu$s in
our setup). Moreover, we also note how the randomness introduced by the
timeouts also makes fairness slightly worse.

Figure 9: Flow completion time in a 16:1 512KiB incast with and without
trimming.

Last, Figure 10 reports the increase in FCT caused by the lack of trimming
support, showing how the additional delay is often smaller than 1 base RTT,
and always within 2 base RTTs on all the scenarios we evaluated. Finally, we
report that the amount of unnecessarily re-transmitted packets is always below
0.2%.

Figure 10: Increase in runtime due to the lack of packet trimming support for
different workloads. Perm. stands for permutation with an oversubscribed
network. The incast are run without over-subscription as it would have little
effect anyway.

Figure 11: Relative incast performance for different incast degrees and
message sizes.

###  4.3 Incast

We first show in Fig. 11 the performance of SMaRTT in incast scenarios ranging
from a 8:1 incast all the way to a 100:1 incast for varying message sizes. We
note that EQDS, being a receiver-based mechanism, can easily achieve the best
performance. Indeed, it can precisely communicate the sending rate to each
sender, and schedule them to be perfectly fair. On the other hand, sender-
based mechanisms tend to suffer more from the randomness of packet drops. We
can see that this is particularly true for small-medium sized messages.
Indeed, small messages do not overrun switch buffers, whereas for large enough
messages all the algorithms have enough time to converge to the correct rate.
The zone is between, usually slightly before BDP is subject to random drop
events that affect sender based mechanism more.

To analyze SMaRTT behavior more in detail, we show in Figure 12 how the queue
size, congestion window, and RTT of a 32:1 incast changes over time. The
figure shows all the different SMaRTT mechanisms being effectively used. When
the application starts, the trimmed packets trigger QuickAdapt. Then, in the
steady state, the RTT is kept close to the target RTT. Eventually,
FastIncrease makes sure that no flow is left behind at the end of the
execution of the incast, by quickly ramping up the congestion windows of the
straggling flows.

Figure 12: The blue lines represent the RTT, the black points the queue size
and the the dashed color lines represent the different windows.

Last, we monitor the impact of using Fair Decrease (FD) and Fair Increase (FI)
on the overall fairness of SMaRTT on a 16:1 16MiB incast. Our results show
that both features significantly improves fairness up to 10% when calculating
the difference between the first and last finishing flow.

###  4.4 Permutation

We show in Fig. 13 the results for a 32MiB permutation traffic pattern on a
4:1 oversubscribed fat tree with 1028 nodes.

From the results, we can see how, once again, for certain small messages
sender-based mechanisms tend to suffer, although the difference here is
relatively small. On the other hand, when increasing the message size, SMaRTT
takes the lead while EQDS gets significantly behind in performance since the
oversubscription causes it to trim a significant amount of packets throughout
the execution. Swift and the variants of SMaRTT perform on average better than
NDP but they are always behind the full SMaRTT implementation.

Figure 13: Flow completion time with a 32MiB permutation with a 4:1 total
oversubscription ratio

If we run the permutation in an even more oversubscribed topology (8:1 total
ratio) we can notice in Figure 1 that the performance of EQDS degrades even
more since it results in a lot more packets being trimmed. To further
emphasize this point, we measure the number of trimmed packets for EQDS and
report that in the worst case scenario just mentioned it can generate up to
155x more trimmed packets than SMaRTT resulting in wasted bandwidth and
resources. The EQDS authors states that in such cases a congestion control
algorithm on the sender side would benefit its performance but we argue that
then SMaRTT is already able to cover both cases well as shown here.

###  4.5 All-To-All

We also evaluate performance for All-To-All communication, a collective
operation commonly used in AI workloads [10.5555/3571885.3571899]. For such
experiment, we use the smaller topology to reduce simulation times and we use
a windowed algorithm for the All-To-All in order to have always at least k
flows active per node. We show the results in an oversubscribed fat tree as a
full fat tree topology is able to handle an all to all without problems for
congestion control.

Figure 14: Using a 4:1 fat tree with 128 nodes. k indicates the number of
active flows at any given time for a sender.

As we can see from Figure 14, in the case of EQDS, the bigger the message, the
more performance it loses compared to SMaRTT or Swift. This is consistent with
the results we previously observed.

###  4.6 Handling Faults and Network Asymmetries

To demonstrate the effectiveness and resilience of entropy recycling in the
presence of faults and asymmetries in a real network environment, we modified
a production-grade FPGA-based RDMA-capable NIC and compared entropy recycling
as implemented in REPS vs a baseline oblivious packet spray approach. The
experimental setup consists of a two-tier fat-tree network, with 100G FPGA-
based NICs and Tomahawk3-based switches. T0 downlinks are 100G and baseline
T0-T1 uplinks are 400G. Endpoints are configured to repeatedly perform ring-
based AllReduce operations consisting of 4MB RDMAs with the logical ring layed
out such that all connections traverse the T1 spine and maximize pressure on
the network.

In the first experiment, there is a total of 16 endpoints connected through
two T0 switches (8 endpoints each) with a total of 4 links to a pair of T1
switches. To demonstrate the adaptiveness of REPS, we changed the link speed
of one of T0-T1 links from 400G to 200G creating asymmetry in the network
(reducing the effective T1 capacity from 1600G to 1200G). Figure 15 shows the
per-flow goodput (end-to-end useful byte rate observed by application, after
header overheads, retransmissions, etc.) for an approach that uses oblivious
packet spray vs. REPS. Oblivious packet spray will send packets across all
paths (including the 200G one) with equal probability and is ultimately capped
by the slower 200G path as the congestion signal produced from the slower path
traffic limits the total flow goodput to the bottlenecked path (thus severely
underutilizing the remaining capacity of the 400G links).

In contrast, REPS can gracefully adapt in such a scenario as the cached
entropies will reflect the network asymmetry and result in a path distribution
that is skewed to tailor to the relative capacity of the available paths. In
this example, REPS is able to reach very high utilization with average per-
flow goodput within 5% of the ideal fair-share target. This adaptivity can
also significantly improve flow completion times in the presence of
asymmetries. Figure 16 shows hardware-collected FCT distributions for the
oblivious packet spray vs. REPS. REPS is able to maintain a much lower and
tighter FCT distribution, significantly reducing average and tail completion
times.

Figure 15: Entropy recycling impact on flow goodput in asymmetric network
Figure 16: Entropy recycling impact on FCT distribution in asymmetric network

To demonstrate the robustness and resilience of REPS in the context of link
failures, Figure 17 shows total packet drops (average across 4 runs each)
observed in a large-scale 128-endpoint run (endpoints split across 2 T0s
connected through 8 T1s) where we abruptly bring down a T0-T1 link in the
middle of the experiment. While the network is trying to recover from the
impact of this event (which in our environment can take in the order of 100s
of milliseconds), oblivious spray will continue sending packets across all
paths (including the ones affected by the link that went down) while REPS will
quickly adapt (within order of RTT) and avoid sending packets down the
affected paths as the entropy cache is replenished from packets that are
traversing healthy paths. In these sample runs, REPS exhibited much more
predictable behavior and was able to significantly reduce the impact of a link
flap and provide an order of magnitude reduction in the total number of packet
drops.

Figure 17: Impact of entropy recycling to link failure recovery

##  5 Conclusion

In this paper, we propose SMaRTT, a sender- and window-based congestion
control mechanism using ECN and delay as congestion signals. If available,
SMaRTT can also take advantage of packet trimming. Otherwise, it falls back to
a timeout-based mechanism, which we show adds at most 2 base RTT of delay. We
couple SMaRTT with REPS, a simple and resource-efficient load balancer that
significantly improves the FCT, as also shown in our evaluation on a real
testbed. REPS, can drastically improve the load balancing performance compared
to traditional per-flow ECMP or oblivious packet spraying while keeping a
simple logic. We also show how REPS is capable of handling effectively faults
and network asymmetries.

We evaluate SMaRTT on several workloads, showing that it outperforms EQDS by
up to 38%. In particular, being SMaRTT sender-based, it has better visibility
and can efficiently handle any type of congestion, while being simple, having
low memory requirements, and not requiring any special support from the
network switches.