Simulate Before Sending:
Rethinking Transport in Datacenter Networks

dcSim should have a near-zero loss probability, despite running in a lossy commodity network. With zero data loss, there is no need to retransmit data, and forward progress is guaranteed.

In modern datacenter networks, “queueing delays and buffer overflow are the root cause of unpredictability” [3]. dcSim should offer a low-queueing solution that enables flexibility to changing patterns.

dcSim should be able to offer per-packet load-balancing to fully utilize the network capacity and address challenging conditions such as failed or congested links.

dcSim should be able to handle several concurrent collectives with many flows simultaneously fighting for a chunk of network capacity.

dcSim should not rely on any non-readily available switch feature.

during which a small Sim (simulation) packet is transmitted through a random path from $S$ to $D$. At each commodity switch along the path, Sims are queued in a Sim queue, distinct from the Data queue for Datas. The Sim queue has strict priority over the Data queue, but its service is rate-limited in a way that allows Sims and Datas to leave in an alternating sequence and fully occupy the line, thus reaching an ideal utilization. Any Sim that arrives at the Sim buffer enters the queue if there is space, and is dropped otherwise. Once a Sim reaches $D$, $D$ sends back a Sim-Ack to $S$.

during which the Datas are sent along the same path previously traversed by their counterpart Sims. To reduce reordering, dcSim associates to each successful Sim the first Data waiting in the queue. This Data is then sent $RT{T}_{\text{max}}$ time after the Sim was sent, where $RT{T}_{\text{max}}$ is a fixed datacenter-wide bound on the Sim RTT (cf. § 2.5). Let’s focus on a specific ${\text{Sim}}_0$ and its corresponding ${\text{Data}}_0$. Assume that ${\text{Sim}}_0$ competes with other Sims for switch buffer occupancy, and manages to get through. Then when ${\text{Data}}_0$ later competes with other Datas, we expect it to have no more competitors than ${\text{Sim}}_0$, and in fact it may have fewer competitors if some Sims got dropped in later switches. We thus expect ${\text{Data}}_0$ to enter the switch buffers and later reach its destination without any drop. That is, we expect the Datas not to experience any drop, and in fact to experience slightly less congestion than their corresponding Sims.

Fig. 1 illustrates the dcSim queueing mechanism, which is implemented at each switch output and at hosts. It consists of a priority arbiter that implements a strict priority without preemption between four queues, dedicated to the four data types in this paper: (i) Sims, (ii) Sim-Acks, (iii) Data-Acks and (iv) Datas. Sim-Acks and Data-Acks acknowledge reception of Sims and Datas, respectively. Sims (serviced at the highest priority) are rate-limited using a token bucket.

The Sims, Sim-Acks, and Data-Acks are small packets of size $\mathrm{\ell }$ (e.g., $\mathrm{\ell }=64\mathrm{bytes}$), and their queues are stored in small buffers with up to $B$ packets each (e.g., $B=12$). Datas are larger packets of size $L$ (e.g., $L=9\mathrm{KB}$ for jumbo packets),¹¹1Each Sim could also generally represent a set of $k$ Data packets. and their buffer size equals the remainder of the allowed buffer size. Since $\mathrm{\ell }\ll L$, the queues for the small packets are extremely unlikely to cause starvation. The packet types can be differentiated in different ways, e.g., using 2 bits out of the 6-bit ToS field in the IP header. The line rate is assumed to be $C$ throughout the datacenter network.

To set the token-bucket rate, we want to determine the ideal bit rates $r_{\text{Sim}}$ for the Sims and $r_{\text{Data}}$ for the Datas. We start with a simple case where there is only one switch in the network and we can neglect the Sim and Data acknowledgments. Assume that the flows are infinite with an infinite stream of Sims and Datas, such that the Sim and Data queues are never empty after the first Sim and Data appear. Also, let $\alpha =\frac{L}{\mathrm{\ell }}$. For example, if $L=9\mathrm{KB}$ and $\mathrm{\ell }=64\mathrm{B}$, then $\alpha \approx 141$. We intuitively want to satisfy two conditions:

1. (1)

   We want to fully utilize the line capacity, i.e., $r_{\text{Sim}}+r_{\text{Data}}=C$.

2. (2)

   We also want the two streams of packets to have the same packet rate, since each successful Sim triggers a later Data. Formally, $\frac{r_{\text{Sim}}}{\mathrm{\ell }}=\frac{r_{\text{Data}}}{L}$, yielding $r_{\text{Data}}=\alpha \cdot r_{\text{Sim}}$.

Putting the two conditions together, we get

Thus, by setting a token bucket of rate $\frac{C}{\alpha +1}$ and size $B$, we expect to achieve these two conditions. This is confirmed in the following theorem (all proofs are in Appendix A).

The token bucket above provides a rate of $\frac{C}{\alpha +1}$ to Sim packets, where the $\alpha$ factor accounts for the Datas and the $1$ accounts for the Sims. However, it neglects the rate of Sim-Acks and Data-Acks. These are harder to account for, as the rates of Sim-Acks and Data-Acks depend on flows that go in the reverse direction. In addition, the Data-Ack rate is lower as dcSim only sends back a Data-Ack every large number of Datas (e.g., 16), leveraging the lack of packet losses. Since we are interested in AI collectives, we expect a mostly symmetric pattern in which the Sim-Ack rate is close to the Sim rate. Therefore, we heuristically set the token bucket rate at

Evaluations show that performance is not sensitive to small variations of this heuristic factor.

At each source host $S$ and for each flow, let $n_{\text{Sim}}$ denote the number of outstanding Sim and Sim-Ack packets in the network, i.e., the number of sent Sim packets for which $S$ has neither received a Sim-Ack nor timed out. Also, let $n_{\text{Data}}$ denote the number of Data packets waiting in the host to be sent. Then $S$ always maintains the inequality

i.e., it makes sure that there are no more outstanding Sims (and Sim-Acks) in the network than available Datas waiting to be sent. As previously explained in § 2.3 and illustrated in Fig. 1, $S$ maintains a Sim buffer of size $B$ that is serviced using a token-bucket policy. $S$ then adds Sims to the Sim queue whenever (i) there is space in the Sim buffer, i.e., the Sim queue size is below $B$ and (ii) there are enough Datas to send a Sim (Equation 3).

We have a degree of freedom in selecting the flows from which to first add Sims. We select flows in round-robin for fairness, but could also have chosen to prioritize flows with the smallest remaining size [5]. Specifically, if there are several collectives and $S$ knows about the collective ID of each of its flows (i.e., roughly speaking, it knows what sets of flows started together), it schedules the next Sim by checking the next collective ID in round-robin order, then choosing a Sim for the next available flow within this collective in round-robin order. If not, it simply picks flows in round-robin order.

Each new Sim is allocated a random path to the destination $D$. Since the datacenter network relies on commodity switches that use ECMP routing, this random-path allocation is widely implemented by allocating a unique random source port to each Sim [23, 9, 25]. dcSim checks that this source port is distinct from that of currently used Sims. The source port changes the flow five-tuple of the Sim, and therefore it alters its ECMP hashed value at each switch, ultimately changing its path.

Upon transmitting a Sim on the line, $S$ (i) records the Sim transmission time, which will also be used to send a Data after a fixed delay; (ii) starts a timeout mechanism; and (iii) increments $n_{\text{Sim}}$. $S$ also increments $n_{\text{Data}}$ when (i) receiving a new Data from the operating system or (ii) a sent Data times out without a received Data-Ack.

In Fig. 2, assume that at time $t$ at source $S$, two Data packets arrive at the queue for destination $D$, so $n_{\text{Data}}=2$. $S$ immediately sends two Sim packets: ${\text{Sim}}_1$ with a random source port that leads to the red path after ECMP hashing, then ${\text{Sim}}_2$ with another random source port that leads to the green path. Thus $n_{\text{Sim}}=n_{\text{Data}}=2.$

At each switch, Sim packets go through the buffer mechanism described in § 2.3. If they encounter a full Sim buffer due to simulated congestion, they are dropped. Else, they reach the destination $D$.

In Fig. 2, the Sim buffer of the leftmost core switch is full, therefore it drops ${\text{Sim}}_1$. In contrast, ${\text{Sim}}_2$ traverses the uncongested green path.

When $D$ receives a Sim, it immediately sends back a Sim-Ack to $S$. As usual, the Sim-Ack destination port and IP address are the Sim source port and IP address. Since ECMP hashing is not symmetric, the Sim-Ack can take an arbitrary path after ECMP hashing of its 5-tuple, until it reaches $S$.

In Fig. 2, $D$ receives ${\text{Sim}}_2$ and sends ${\text{Sim-Ack}}_2$ back to $S$ through the blue path.

When a source $S$ receives a Sim-Ack for some Sim, it immediately associates the Sim to the first of the Data packets waiting in $S$ to be sent. $S$ updates

where the first line implies that the Data will take the same path as its corresponding Sim, and the second line means that the Data is scheduled to be transmitted after a fixed delay $RT{T}_{\text{max}}$ (defined in § 2.5) following the transmission time of its Sim. $S$ also decrements $n_{\text{Sim}}$ and $n_{\text{Data}}$. When sending the Data, $S$ also sets a large timer and keeps the Data in a side buffer, so that in the rare event that the Data times out without an acknowledgment, it will be inserted back at the head of the queue of Data packets waiting to be sent.

In Fig. 2, $S$ receives ${\text{Sim-Ack}}_2$. Thus, it associates ${\text{Sim}}_2$ with ${\text{Data}}_1$, the first Data in the queue. If ${\text{Sim}}_2$ was sent at time $t$, then ${\text{Data}}_1$ is later sent at time $t+RT{T}_{\text{max}}$ along the same green path. In addition, as detailed later, ${\text{Sim}}_1$ times out and a new Sim with a new random path can be sent instead.

Note that this example illustrates well why the association between Data and Sim packets is not made at the creation of the Sim packets, as would be intuitive. If ${\text{Data}}_1$ were associated to ${\text{Sim}}_1$, then after ${\text{Sim}}_1$ is dropped, it would need to wait for a timeout and then generate a new Sim, while the following ${\text{Data}}_2$ packet in the queue would be released upon the arrival of ${\text{Sim-Ack}}_2$. This could cause severe reordering in the system.

$D$ sends a Data-Ack back to $S$ every large number of Datas (e.g., 16), leveraging the non-existent loss rate in the network (with some minimum frequency, e.g., once every 3 propagation RTTs). (This is not illustrated in Fig. 2.)

When $S$ receives a Data-Ack, it deletes the Data. Else, as mentioned, if a Data times out, it is put back in the queue of Datas waiting to be sent. In addition, if a Sim timer expires, it decrements $n_{\text{Sim}}$, enabling the transmission of a new Sim.

In Fig. 2, when the timeout for ${\text{Sim}}_1$ that was set in ➀ expires at $t+RT{T}_{\text{max}}$, $S$ assumes that ${\text{Sim}}_1$ is lost and decrements $n_{\text{Sim}}$. A new Sim with a new random path can then be sent to $D$.

To summarize, $S$ needs to manage four Data queues, as Datas can be in four states: (1) at first, waiting for a Sim to be sent; then (2) after receiving a Sim-Ack, waiting for a green light to transmit $RT{T}_{\text{max}}$ after the Sim; then (3) queued in the Data queue and ready to be transmitted, potentially waiting for other Datas or Sims currently being transmitted; as well as (4) with a copy stored in a side buffer in case a Data-Ack does not come back on time and the timeout expires.

Assume that $H=6\mathrm{hops}$ in a three-level fat-tree topology, $RT{T}_p=7.8\mu \text{s}$, $C=800\mathrm{Gbps}$, $L=1.5\mathrm{KB}$, $\mathrm{\ell }=64\mathrm{B}$, and $B=12\mathrm{pkts}$. Then $\alpha =\frac{1,500}{64}=23$ and $RT{T}_{\text{max}}=1.32RT{T}_p=10.3\mu \text{s}$.

Let’s provide intuition for why we cannot generalize results from a single switch to the whole network. As explained in § 2.2, a Sim denoted ${\text{Sim}}_0$ may compete with other Sims for a place in the Sim queue. However, these other Sims may be dropped in later switches, completely changing the timing and effectively canceling the effects of reservation. Thus, when the ${\text{Data}}_0$ corresponding to ${\text{Sim}}_0$ arrives after $RT{T}_{\text{max}}$, it may not need to compete with other Datas anymore, because their Sims were dropped. Hence, it may quickly exit the switch and arrive earlier than ${\text{Sim}}_0$ at the next switch. However, the next switch may currently be congested, leading to ${\text{Data}}_0$ being dropped.

Fig. 3 illustrates a counterexample, assuming the Data buffer can only hold $B$ packets like the Sim buffer. It follows a switch buffer slot-by-slot, where each slot of duration $\delta$ corresponds to the time between tokens in the Sim token-buffer mechanism (i.e., $\delta =\frac{L+2.1\mathrm{\ell }}{C}$, following Equation 2). It shows that while the Sim for source host $C$ goes through the switch seamlessly, its Data actually needs to be dropped.

In practice, the above counterexample means that we can only expect a practical near-zero loss rate, not a deterministic zero-loss guarantee. For example, in evaluations (§ 4), we found that if the Data buffer can hold about $2\times$ as many packets as the Sim buffer, then we could not see a single Data loss, no matter the traffic pattern and the network oversubscription.

We implement dcSim in the dcPIM simulator [55], and evaluate it against dcPIM, pHost and pFabric.²²2dcPIM has been shown [10] to have superior performance vs. Homa [37], Aeolus [19], NDP [17, 48] and HPCC [29] in various settings, therefore we do not repeat comparisons against these algorithms. The dcSim source code is available online [53].

We employ a 3-layer fat-tree topology [4] with a switch radix $k=8$, resulting in a network consisting of 128 end-hosts, 32 edge switches, 32 aggregation switches, and 16 core switches. All links are configured with 800 Gbps bandwidth, as commercially available today [40], and jumbo frames of $9\mathrm{KB}$. We use the simulator default settings for the other parameters: each link propagation delay is set to 200 ns, and each switch is configured with a buffer size of $500\mathrm{KB}$ per port and a processing latency of 450 ns, yielding a zero-load RTT of $7.8\mu \text{s}$. For dcSim, we set a constant Sim buffer size of $B=12$ packets, reflecting our goal of keeping low queueing occupancies. When evaluating small buffer sizes below $250\mathrm{KB}$ (equivalent to 28 Data packets), we reduce $B$ proportionally to the buffer size, ensuring that the Sim and Data buffer sizes decrease in lockstep.

We also test the algorithms using an oversubscribed (blocking) topology [54] where half the core switches are removed.

We focus on collective communication patterns that are representative of AI training workloads, and add the functionality to the simulator. A collective is defined as a set of flows that begin transmission simultaneously. We implement the following collectives:

The permutation pattern models a ring all-reduce collective algorithm. Each sender sends a single flow to a single receiver, and each receiver receives a single flow from a single sender, yielding a total of $n$ flows when there are $n$ hosts in the collective. Each single collective always uses all the hosts ($n=128$).

The all-to-all pattern models tensor parallelism. All hosts in the collective send a flow to all other hosts, yielding $n(n-1)$ flows per collective of size $n$. We also evaluate an infinite all-to-all workload where each flow has an infinite size.

The all-to-all variable (all-to-all-v) pattern models mixture of experts (MoE) traffic [33, 32, 21, 22, 13, 30, 51]. It is similar to all-to-all, but can be highly unbalanced. To model it, each packet from each sender chooses a random receiver out of the $n-1$ other hosts in the collective.

To reflect several competing MoE collectives or tenants, we also focus on a set of several collectives of different sizes that operate in the same datacenter network, as competing collectives are known to be hard to service [49, 32, 26, 58]. We define a baseline set as using all-to-all-v with 5 collectives, with collective sizes randomly selected from the set $\{8,16,32,64\}$, possibly with hosts sharing several collectives, and flow sizes of $2\times$ bandwidth-delay product (BDP). We then vary these parameters to study their impact.

We measure the: (1) Collective completion time (CCT), i.e., the time at which the last packet of a collective reaches its destination. When there are several collectives, we average over all CCTs. (2) Packet loss rate. (3) Total queueing delay, i.e., the total time from the transmission time at the source host to arrival time at the destination host for data packets. (4) Reordering size, i.e., the number of data packets per measurement interval that arrive at the destination with non-maximal sequence number. We measure it because in the selective-repeat algorithm and in practical hardware implementations, when there is high reordering, the difference between the sent and received orders of several packets can exceed the transmit window, thus throttling throughput and leading to network underutilization. (5) Utilization, i.e., the quantity of data received in a time interval, divided by the total link capacity of the hosts.

We run each simulation 20 times and plot the average result, together with the standard error of the mean (SEM) as error bars.

Fig. 4 illustrates the performance of dcSim compared to dcPIM, pFabric and pHost in an infinite all-to-all traffic pattern. The network utilization of dcSim remains higher than in the other algorithms by at least 14% (Fig. 4(a)). The lower utilization of pFabric may be due to its high level of packet drops. dcSim also impressively achieves 0% loss and 0% packet reordering at all times (Figs. 4(b) and 4(c)). dcSim’s low reordering throughout the evaluations may be due to two main reasons. First, its lower queueing delay, as seen in several evaluations. Second, the fact that when sending a burst of Sims through several paths then receiving the Sim-Acks back, Datas are later selected in the order in which Sim-Acks were received, e.g., the first Data is sent on the shortest path. It makes it less likely for a later Data to pull ahead. In contrast, dcPIM and pHost are able to remain lossless, but decrease their sending rate as they detect congestion in the network, based on received token packets.

Fig. 5 illustrates the CCT with either a single permutation or a single all-to-all collective for different flow sizes. The flow sizes are presented as multiples of BDP, where BDP represents 87 packets. As expected, for all algorithms, CCT increases when the flow size increases. dcSim completes faster than dcPIM, pFabric and pHost in all experiments, except for an half-BDP size in the permutation traffic. This evaluation is the least congested of all. Under 1 BDP, dcPIM does not activate its full algorithm for small flows, and therefore simply sends the flows without any control packets. dcSim’s focus is on larger flows for AI training, but it could adopt the same behavior for small flows by sending them at a lower priority without using Sim packets. Above 1 BDP, the dcPIM algorithm is activated, worsening the CCT. On the other hand, with the heavier all-to-all traffic (Fig. 5(b)), the non-activation of dcPIM for short flows of size $0.5\times \mathrm{BDP}$ increases dcPIM’s CCT even beyond that of pFabric and pHost.

Fig. 6 presents the results of running a single all-to-all-v collective as a function of different average flow sizes. Since flow sizes vary, we only consider their average, and express it again as a multiple of BDP. dcSim uniformly achieves lower CCTs, with an average improvement of 12.5%, together with a zero loss rate and reordering size, and a small queueing delay.

Fig. 7 presents an evaluation with five concurrent collectives of random sizes. Performance is largely similar to a single all-to-all-v, with a non-zero yet negligible reordering size. Given the lower total load, dcPIM’s queueing delay also gets lower and similar to dcSim. pHost achieves the lowest queueing delay due to its conservative schedule, which comes at the cost of a higher CCT.

Fig. 8 illustrates an adverse scenario with an oversubscribed network in the baseline scenario of five all-to-all-v collectives. We effectively halve the number of core switches by retaining only the odd-indexed switches and reducing the rate of the remaining one to 1% of their initial rate. dcSim excels in this case, with markedly better performance than the other algorithms. The simulation phase enables dcSim to detect and avoid congested paths by dropping Sim packets early, thereby preventing subsequent Data packet losses. In contrast, dcPIM schedules end-to-end links between two hosts but cannot identify whether one path is better than another, since it has no visibility inside the network. Some aggregation switches are much more congested than others, therefore load-balancing cannot be made blindly. Once congestion is detected, dcPIM reduces the total sending rate to limit losses, but then does not utilize the full network capacity.

Fig. 9(a) compares the CCT when using some of the most common Data packet sizes in datacenter networks: $1.5\mathrm{KB}$ (Ethernet), $4\mathrm{KB}$ (RDMA), or $9\mathrm{KB}$ (Jumbo). As expected, for all algorithms, the CCT is lower when $L$ is higher, i.e., larger packets help with bulky transfers. While we used $9\mathrm{KB}$ as the default packet size in our evaluations, dcSim actually outperforms other algorithms even more for lower packet sizes.

Fig. 9(b) illustrates the impact of reducing the switch buffer sizes. dcSim is resilient to this reduction, and results are largely similar to previous evaluations.

Fig. 9(c) varies the number of all-to-all-v collectives. dcSim keeps outperforming, and outperforms even more at high loads with many collectives.

Fig. 9(d) illustrates the impact of the maximum collective size, given five random all-to-all-v collectives. dcSim keeps outperforming in all cases.

We rely on an $RT{T}_{\text{max}}$ delay given by an internal clock. We evaluated the resilience of our system to clock drift using a methodology similar to that employed in Firefly [28]. Fig. 9(e) demonstrates that the impact on CCT remains negligible, with a performance degradation of less than 1% even under a static drift of $40\mathrm{PPM}$.

Fig. 10(a) illustrates the correlation in a random last-hop switch between the rate of Sim packets and the rate of Data packets with shifted times, in order to verify that the rate of Data packets corresponds indeed to the earlier rate of Sim packets. We consider a last-hop (edge switch $\to$ host) switch queue to reduce the impact of Sims that may be later dropped. The correlation achieves a maximum value of 0.77, confirming that the Data rate indeed reflects the Sim rate, even though the match is not entirely perfect. In addition, the corresponding time lag is $0.86RT{T}_{\text{max}}$. The intuition for a lag lower than $RT{T}_{\text{max}}$ is that the Sim drops along the path lead to lower queueing delay for the Datas, which reach the last-hop queue faster.

In addition, Fig. 10(b) shows the dynamic behavior of the Sim and (lagged) Data queues. They clearly tend to move together consistently, indicating that it is not unreasonable to assume in general that if the Sim buffer is not congested, then neither should the Data buffer.

Fig. 11 shows the impact of the Data buffer size on the loss rate, given a constant Sim buffer size that can hold $B=12$ Sim packets. Let $B_{\mathrm{Data}}$ denote the number of Datas that can fit in the Data buffer size. Then the figure shows that for

there is no loss, i.e., if the Data buffer can fit 24 Datas, no Data will be lost despite the high load of five all-to-all-v collectives. While the lossless threshold is not at an ideal $\frac{B_{\mathrm{Data}}}{B}=1$ that would correspond to an exact emulation, it is still an impressive result that the network can run lossless with so little buffering.

dcSim sends each Data packet $RT{T}_{\text{max}}$ after its corresponding Sim was sent. We introduce an Async dcSim version that acts impatiently and immediately sends the Data packet after a Sim-Ack arrives at the source. Async dcSim is intriguing, because on the one hand, it loses the theoretical synchronization, but on the other, it is more reactive to changes in network conditions.

Fig. 12 shows how the CCT of Async dcSim is slightly lower than the CCT of the regular dcSim. Its loss rate is also 0%, and its queueing delay is lower by up to 24%, as it is more likely to quickly exploit a low queue size. However, since it is not synchronized anymore, its number of reordered packets becomes much higher, indicating a higher disparity in the queue sizes between different paths. Thus, this Async version offers different tradeoffs for the datacenter operator.

dcSim waits $RT{T}_{\text{max}}$ to send Data packets, where $RT{T}_{\text{max}}$ is computed according to the worst-case formula of Theorem 2. Motivated by the findings in Async dcSim, we analyze the impact on system performance of only waiting for a fraction of the worst-case $RT{T}_{\text{max}}$. More specifically, we send the Data packet at the later of (1) this fractional delay following the Sim transmission and (2) the Sim-Ack arrival time.

Fig. 13 compares this fractional dcSim for several fractional $RT{T}_{\text{max}}$ values against the original dcSim and Async dcSim. It shows that the CCT of the fractional dcSim is marginally lower than for the baseline dcSim, while its packet loss remains at 0%. In addition, its queueing delay decreases. However, packet reordering increases, maybe because we are slowly losing the guarantee provided by $RT{T}_{\text{max}}$. We observe that queueing and reordering behavior remain comparable to the baseline dcSim from $RT{T}_{\text{max}}$ down to $0.85RT{T}_{\text{max}}$, while the behavior converges towards that of Async dcSim as $RT{T}_{\text{max}}$ is further reduced.