
\section{Studying Error Sources} \label{s:app-error-sources}

\begin{figure}[t]
    \centering
    \includegraphics[width=0.9\linewidth]{figs/parking-lot.pdf}
    \vspace{-2mm}
    \caption{\small
        The parking lot topology used in \Sec{app-error-sources}.
        %
        In this topology, zero sends to six, one sends to two, three sends to
        four, and five sends to six.
        %
        We refer to the traffic from zero to six as \emph{main traffic} and to
        all other traffic as \emph{cross traffic}.
        %
        The bolded red links contain both main traffic and cross traffic, and
        we call them \emph{congested links}.
    }
    \label{fig:parking-lot}
    \vspace{-4mm}
\end{figure}

Recall from \Sec{error-sources} that \texttt{Parsimon}\xspace's approximations induce errors in
its end-to-end estimates.
In this appendix, we use microbenchmarks to study the effects of some
pathological cases on \texttt{Parsimon}\xspace's accuracy.
For an initial discussion on these topics, please refer to \Sec{error-sources}.

Throughout, we use the parking lot topology shown in \Fig{parking-lot} with 40
Gbps links.
The flow of traffic through the topology is shown with arrows and described in
the caption.
We refer to the traffic from node zero to node six as \emph{main traffic} and
to all other traffic as \emph{cross traffic}.
The bolded red links contain both main traffic and cross traffic, and we call
them \emph{congested links}.
In all experiments, we set the load of the main traffic to 25\%.
When there is cross traffic, its load is also 25\%, yielding a total load of
50\% on all three congested links.
Lastly, to isolate the effects on the main path from zero to six, we measure
FCT slowdown distributions only for the main traffic.

\subsection{First-Hop Delays} \label{s:first-hop-delays}

\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{figs/first-hop-delays.pdf}
    \vspace{-8mm}
    \caption{\small
        CDFs of FCT slowdown estimated by ns-3 and \texttt{Parsimon}\xspace for the main traffic,
        both with and without cross traffic.
        %
        When there is cross traffic, errors arising from first-hop delays are
        second-order, as most delays are cause by queueing on the congested
        links.
        %
        However, when there is no cross traffic, those errors become dominant.
        %
        The graph on the right uses the same workload as the one on the left,
        except the cross traffic is removed.
        %
        Note the different x-axes.
    }
    \label{fig:first-hop-delays}
    \vspace{-4mm}
\end{figure}

First, consider the case where all traffic in \Fig{parking-lot} originates from
node zero and is destined to node six, and recall that all links have the same
capacity.
In a real network, all queueing in this scenario would occur at the first hop.
Subsequent hops would see traffic completely smoothed, and they would therefore
contributing zero queueing delay.

If we re-examine how link-level topologies are constructed in \Fig{link-level},
we see that this smoothing effect is captured, since all traffic passes through
edge links with the original edge-link capacities.
However, for the link-level topologies in cases B and C of \Fig{link-level}, it
is possible for first-hop edge links to contribute delays that will be
(erroniously) attributed to the target link.
In most cases, we expect the magnitude of this error to be small.
A target link will almost always have multiple sources, and only the traffic
passing through the target link is simulated.
Consequently, the first-hop delays in link-level simulation are expected to be
small compared to delays accrued at target links.

The scenario which we first described---in which all traffic on a path
originates from a single source---represents the worst case.
Here, all target links (aside from the first hop) contribute no queueing delay,
thus magnifying the error induced by repeatedly counting the first-hop delays
for each target link.
\Fig{first-hop-delays} shows this effect.
In this experiment, the main traffic consists of one kilobyte flows, and the
cross traffic consists of 10 kilobyte, 20 kilobyte, and 40 kilobyte flows for
hosts one, three, and five, respectively.
All traffic follows a Poisson arrival process.
With cross traffic, we see from the graph on the left that \texttt{Parsimon}\xspace accurately
estimates the FCT slowdown distribution of the main traffic.
However, when we remove the cross traffic, as done to produce the graph on the
right, we see substantial error in \texttt{Parsimon}\xspace's estimates due to the first-hop delays
previously described.
We note that this error exists \emph{even when there is cross traffic}, but the
error contributes so little to total delays---which are dominated by queueing
at congested links---that \texttt{Parsimon}\xspace still maintains good accuracy.

\subsection{Correlated and Simultaneous Delays} \label{s:correlations}

\begin{figure}[t]
    \centering
    \begin{subfigure}[t]{\linewidth}
        \centering
        \includegraphics[width=\textwidth]{figs/short_corr.pdf}
        \vspace{-4mm}
        \caption{\small
            Short flows (1 KB), Poisson cross traffic
        }
        \label{fig:short-corr}
    \end{subfigure}
    \hfill
    \begin{subfigure}[t]{\linewidth}
        \centering
        \includegraphics[width=\textwidth]{figs/long_corr.pdf}
        \vspace{-4mm}
        \caption{\small
            Long flows (400 KB), Poisson cross traffic
        }
        \vspace{-1mm}
        \label{fig:long-corr}
    \end{subfigure}
    \caption{\small
        CDFs of FCT slowdown estimated by ns-3 and \texttt{Parsimon}\xspace for the main traffic
        with regular or identical cross traffic.
        %
        The main traffic consists either of short flows (\Fig{short-corr}) or
        long flows (\Fig{long-corr}).
        %
        When delays are artifically correlated by replicating the same cross
        traffic across hosts, accuracy decreases for both short and long flows,
        with long flows seeing larger errors.
        %
        In fact, long-flow estimates have significant error even when delays
        are not explicitly correlated; this is due to the simultaneous delays
        induced by the smooth Poisson cross traffic.
    }
    \label{fig:corr-poisson}
    \vspace{-2mm}
\end{figure}

\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{figs/long_corr_2.pdf}
    \vspace{-8mm}
    \caption{\small
        CDFs of FCT slowdown for the same scenario as in \Fig{long-corr}, but
        with bursty cross traffic (log-normal inter-arrival times, $\sigma=2$).
        %
        When the cross traffic is bursty, long flows experience fewer
        simultaneous delays with regular cross traffic.
        %
        This results in less error in \texttt{Parsimon}\xspace's estimates.
    }
    \label{fig:long-corr-2}
    \vspace{-4mm}
\end{figure}

Next we examine the effect of correlated and simultaneous delays on \texttt{Parsimon}\xspace's
accuracy.
We begin by artificially correlating delays and examining the effect on
estimated slowdown distributions.
Note that if the delays along a path are positively correlated---for example,
if the probability of encountering delay at hop $i+1$ is higher given there is
delay at hop $i$---then we also expect to see more simultaneous delays along
the path.
We create these correlated delays by modulating the cross traffic.
For regular unmodified cross traffic, we use the same setup as in the previous
subsection (\Sec{first-hop-delays}).
To artificially correlate delays, we replicate the exact sequence of flows from
source one on sources three and five in \Fig{parking-lot}, so that all three
sources of cross traffic send the same flows at the same time.
This produces an extreme case of correlation.

Because short-flow and long-flow estimates have different sources of error,
we separate the two cases when generating the main traffic.
For short flows we use the same one kilobyte flows as before, and for long
flows we generate flows that are 10 times the maximum bandwidth-delay product, or 400 kilobytes.
\Fig{corr-poisson} shows the effect of correlating delays on \texttt{Parsimon}\xspace's accuracy
for short and long flows.

\Para{Short-flow main traffic.}
In the case of short flows (\Fig{short-corr}), a chief effect of increased
correlation is to alter the probability that a flow will encounter queueing.
For example, suppose a short flow traverses only two links at 50\% utilization.
If the delays of the two links are independent, we can estimate the probability
that the flow encounters no delay ({i.e.},  no queueing) as $50\% \times 50\% = 25\%$.
However, if the delays are perfectly positively correlated, then the
probability that the flow encounters no delay increases to 50\%.
\texttt{Parsimon}\xspace does not capture this effect because it treats all links independently; in
this experiment, this manifests as slight overestimates in FCT slowdown
distributions.

\Para{Long-flow main traffic.}
While the total delay for a short flow can be thought of as the sum of
individual link delays, the same reasoning does not straightforwardly extend to
long flows.
Unlike a short flow, a long flow occupies multiple hops at the same time, and
only the bottleneck at each instant contributes to end-to-end delay.
Summing link delays is therefore only appropriate if different hops contribute
significant delays at largely different times.
However, \texttt{Parsimon}\xspace always aggregates individual link contributions by adding them,
regardless of whether a link was the bottleneck when the delay was incurred.
When we turn our attention to \Fig{long-corr}, we see that not only is the
effect of identical cross traffic more severe, but also there is significant
error even with regular cross traffic.
This is because the cross traffic is smooth (recall that it uses uniform flow
sizes and a Poisson arrival process).
Smooth traffic results in small but frequent delays at congested links,
increasing the chance that long flows will experience simultaneous delays.

In \Fig{long-corr-2}, we duplicate the scenario in \Fig{long-corr}, except we
make the cross traffic bursty by using a log-normal inter-arrival time
distribution with shape parameter $\sigma=2$.
Because the cross traffic is bursty, there is less simultaneous delay in the
regular case, and the induced error is no longer dominant.
Consequently, \texttt{Parsimon}\xspace's estimates are closer to the ground truth in the graph on
the left.
Identical cross traffic still induces large and frequent simultaneous delays,
so the errors remain in the graph on the right.

\section{Clustering Details} \label{s:more-clustering}

Here we briefly describe the distance function and the thresholding critera we
use in the evaluation (\Sec{eval}) for clustering link-level simulations.
First, recall from \Sec{clustering} that the link features we extract are 1)
the average load, 2) the flow size distribution, 3) the inter-arrival time
distribution.
For any two links, we compute distances between their features, and we cluster
the links together if the distances are under some threshold.

\Para{Distance functions.} To compute a distance between link loads, we compute
the error.
If $a$ and $b$ are two link loads, error $e$ is computed as
\begin{equation*}
    e = \frac{|a - b|}{a}.
\end{equation*}
To compare distributions, there are many options.
We opt for a function that is 1) easily interpretable, 2) scale-independent,
and 3) adequately captures differences in the tail.
To compute a distance between two distributions, we extract 1,000
percentiles from each of them, and we compute a weighted mean absolute
percentage error (WMAPE) between them.
Suppose $A$ and $B$ are the sequences of extracted percentiles.
Then, WMAPE is computed as
\begin{equation*}
    \text{WMAPE} \ = \ \frac{
    \sum_{i=1}^{n} |A_{i} - B_{i}|
    }{
    \sum_{i=1}^{n} |A_{i}|
    }.
\end{equation*}

\noindent For our purpose, $A_{i}$ and $B_{i}$ are non-negative for all $i$.
We note it is a bit counterintuitive for our distance functions not to commute.
However, we have found that it is easy to set thresholds for these metrics, and
they produce adequate clustering for the workloads under study.

\Para{Distance thresholds.} Recall that we only want to cluster two links
together if we expect their simulation outputs to be similar.
Consequently, when setting a threshold for link loads we must consider the
network and the workload being assessed.
At high load, small differences in link loads can yield large differences in
the tails of FCT distributions; in these cases, we typically set tighter
thresholds to preserve accuracy (as usual, this is subject to a speed-accuracy
trade-off).
For highly-loaded networks, we commonly require $e < 0.001$ or $e < 0.002$ for
links to be clustered together.
Ideally, this decision would be made on a link-by-link basis, so that tighter
thresholds would be set only for high-load links---doing so may allow for more
liberal clustering of the low-load links contributing little delay, resulting
in more pruned simulations.
However, the current prototype sets a single threshold per simulation.
To set a threshold between distributions, we typically require $\text{WMAPE} <
    0.1$.




\section{Background and Motivation}

\kz{
    full-fidelity simulation slow because dependencies between events have to
    be respected, reducing chances for parallelization.
    also it's slow because application, transport, network, and link layers are
    modeled. even if you don't need them you still pay for them out of the box.
    full-fidelity simulation cannot be effectively parallelized (MimicNet).
    flow-level approximations: most assume flows reach steady-state
    immediately, then solve a bandwidth sharing problem. this becomes less
    accurate with higher link speeds (MimicNet eval used 100Mbps, and it still
    wasn't accurate).
    don't know of any flow-level simulators that model queues; don't want to
    claim too much here.
    maybe more comments on MimicNet.
}
\section{Conclusion}
In this paper, we propose and evaluate a new method
for computing a conservative estimate of flow-level tail latency
for large scale data center networks, given an arbitrary
traffic matrix, topology, flow size distribution, and inter-arrival
process. Our approach decomposes the problem into a large number of
individual link simulations, specially constructed
to produce accurate estimates of the probability distribution of
delay contributed by congestion at each link.  We then mechanically combine these
link-level delay distributions to produce flow-level estimates.
On a large-scale network using a commercial workload,
our approach outperforms ns-3 by a factor of 492
on a single multicore server with a loss of accuracy of
less than 9\% in the tail of the latency distribution.


\section{Discussion}

\kz{
    From Mohammad: maybe slightly-longer-than-usual discussion of what you
    could use this for.
}
\section{Evaluation} \label{s:eval}

\texttt{Parsimon}\xspace's goal is to quickly estimate tail latencies for a variety of large
data center networks and workloads.
In evaluating \texttt{Parsimon}\xspace, we would like to assess 1) \texttt{Parsimon}\xspace's accuracy and performance
at the scale of thousands of hosts, and 2) how accuracy is affected by a wide
range of variables over the workload and the topology.

Our strategy is as follows.
Using workloads extracted from industry datasets, we start with a
384-rack, 6144-host topology to evaluate \texttt{Parsimon}\xspace's speed and accuracy in one
scenario at scale.
Then, to evaluate nearly 200 other topology and workload scenarios, we
downsample the workload so that it can run on a smaller 256-host topology.
This allows us to run enough ns-3 simulations quickly enough to perform a detailed sensitivity
analysis.

\subsection{General Setup} \label{s:eval-setup}

\begin{figure*}[t]
    \centering
   
    \begin{subfigure}[t]{0.342\linewidth}
        \centering
        \includegraphics[width=\textwidth]{figs/matrices.pdf}
        \vspace{-6mm}
        \caption{\small
            Traffic matrices (32-rack sample)
        }
        \label{fig:matrices}
    \end{subfigure}
    \hfill
    \begin{subfigure}[t]{0.241\linewidth}
        \centering
        \includegraphics[width=\textwidth]{figs/flow-sizes.pdf}
        \vspace{-6mm}
        \caption{\small
            Flow size distributions
        }
        \label{fig:flow-sizes}
    \end{subfigure}
    \hfill
    \begin{subfigure}[t]{0.40\linewidth}
        \centering
        \includegraphics[width=\textwidth]{figs/link-loads.pdf}
        \vspace{-6mm}
        \caption{\small
            Normalized link load distributions
        }
        \label{fig:link-loads}
    \end{subfigure}
    \vspace{-3mm}
    \caption{\small
        In the evaluation, we model workloads using data from Roy {\em et al.}\xspace's study
        of Meta's data center network~\cite{fb-network}.
        %
        The traffic matrices in \Fig{matrices} are extracted from the
        accompanying dataset, and the flow size distributions in
        \Fig{flow-sizes} are estimated from the published data.
        %
        Lastly, for a given topology, the distribution of link loads depends on
        1) the traffic matrix and 2) the degree of oversubscription.
        %
        \Fig{link-loads} shows the link loads induced by the matrices in
        \Fig{matrices} on two 32-rack topologies with different
        overprovisioning.
        %
        The x-axis is normalized to the maximum link load.
    }
    \vspace{-3mm}
    \label{fig:workload}
\end{figure*}

\begin{table}
    \small
    \centering
    \begin{tabular}{lcc}
        \toprule
        Variant   & Clustering? & Link-level backend \\
        \midrule
        \texttt{Parsimon}\xspace      & No          & custom             \\
        \texttt{Parsimon}\xspace/C    & Yes         & custom             \\
        \texttt{Parsimon}\xspace/ns-3 & No          & ns-3               \\
        \texttt{Parsimon}\xspace/inf  & ---         & custom             \\
        \bottomrule
    \end{tabular}
    \caption{\small
        The \texttt{Parsimon}\xspace variants under consideration.
        %
        \texttt{Parsimon}\xspace/inf is a variant that assumes infinite cores and memory.
    }
    \vspace{-10mm}
    \label{tab:variants}
   
\end{table}

Each scenario we consider has six components: 1) a topology size, 2) an
oversubscription factor, 3) a traffic matrix, 4) a flow size distribution, 5) a
burstiness level, and 6) a maximum load level.
Here, we briefly describe how these are specified and configured.
We also discuss which \texttt{Parsimon}\xspace variants we will assess and how we establish a
baseline.

\Para{Topology and oversubscription.} To mimic an industry topology, our
topologies are modeled after Meta's data center
fabric~\cite{fb-fabric}.
In brief, there are three layers of switches: hosts connected to a top-of-rack
switch (ToR) with 10 Gbps links constitute a \emph{rack}, racks connected to
each other via fabric switches with 40 Gbps links constitute a \emph{pod}, and
pods connected to each other via spine switches with 40 Gbps links constitute a
\emph{cluster}.
Spine switches are organized in \emph{planes}.
We can modulate the size of a topology (corresponding to a cluster)
by adjusting the number of pods, the number of racks per pod, and the number of
hosts per rack, and we can modulate the oversubscription factor by adjusting
the number of spines per plane.

\Para{Traffic matrices.} The traffic matrices are extracted from the datasets
accompanying Roy {\em et al.}\xspace's study of Meta's data center network~\cite{fb-network}.
The data only allow us to construct reliable rack-to-rack matrices.
When sampling workloads, we use the matrices to generate rack-to-rack traffic,
but once a rack is chosen, we select its hosts uniformly at random.
This may bear semblance to reality: according to Roy {\em et al.}\xspace, Meta's racks
typically only contain servers in the same role, and load balancing is used
pervasively.
We use traffic matrices from three different clusters: a database cluster
(matrix A), a web server cluster (matrix B), and a Hadoop cluster (matrix C).
\Fig{matrices} shows 32-rack samples of the matrices.

\Para{Flow sizes and burstiness.} We use three flow size distributions,
estimated from published data in Roy {\em et al.}\xspace's study~\cite{fb-network}.
These are reproduced in \Fig{flow-sizes}.
For inter-arrival times, we use the log-normal distribution to model bursty
traffic, and we modulate the burstiness by adjusting the log-normal shape
parameter $\sigma$.
For low burstiness, we select $\sigma = 1$, and for high burstiness, we choose
$\sigma = 2$.

\Para{Maximum load level.} When setting a load level, we ensure that the offered rate is less than the link
capacity for each link by specifying the maximum load level that any link can have.
Note that a given maximum load level may result in
different link load distributions, depending on the traffic matrix and the
topology.
\Fig{link-loads} shows the distribution of normalized link loads on a 32-rack
topology with the traffic matrices in \Fig{matrices} and two different
oversubscription factors.
When describing how loaded a topology is, we will usually specify
the average load of the top 10\% most loaded links.

\Para{\texttt{Parsimon}\xspace variants and baseline.} To establish a baseline for \texttt{Parsimon}\xspace's accuracy
and performance, we use ns-3 with the optimized build profile.
We also consider several \texttt{Parsimon}\xspace variants, summarized in \Tab{variants}.
By default, \texttt{Parsimon}\xspace uses the custom link-level backend (\Sec{fast-sim}) with
clustering turned off.
This expresses a lower bound on \texttt{Parsimon}\xspace's expected speed-up given a particular
machine.
\texttt{Parsimon}\xspace/C adds clustering to the default variant using the methods described at
the end of \Sec{clustering}, and \texttt{Parsimon}\xspace/ns-3 replaces the default's custom
backend with ns-3.
Lastly, \texttt{Parsimon}\xspace/inf provides an estimate of \texttt{Parsimon}\xspace's performance given infinite
cores and infinite memory, computed by adding the run time of the longest
link-level simulation to the fixed costs of network setup and convolution
sampling.
This represents an upper bound on the \texttt{Parsimon}\xspace's achievable performance.
All performance measurements are taken on a 32-core AMD Ryzen Threadripper
3970X.

\subsection{Analysis on a Large-Scale Network} \label{s:large-scale}

\begin{figure*}[t]
    \centering
   
    \includegraphics[width=\linewidth]{figs/large-scale.pdf}
    \vspace{-7mm}
    \caption{\small
        CDFs of FCT slowdown estimated by ns-3 and two \texttt{Parsimon}\xspace variants (note the
        y-axis).
        %
        On a large network with 6,144 hosts, an industry traffic matrix (matrix
        B), and 2-to-1 oversubscription in the core, \texttt{Parsimon}\xspace's latency estimates
        are similar to those produced by full-fidelity simulation.
        %
        \Tab{large-scale} shows the performance of each estimator.
    }
    \label{fig:large-scale}
    \vspace{-2mm}
\end{figure*}

\begin{table}
    \small
    \centering
    \begin{tabular}{p{2cm}>{\raggedleft\arraybackslash}p{1.6cm}>{\raggedleft\arraybackslash}p{1.6cm}}
        \toprule
        Estimator & Time        & Speed-up     \\
        \midrule
        ns-3      & 10h 48m 26s & ---          \\
        \texttt{Parsimon}\xspace      & 4m 13s      & $154\times$  \\
        \texttt{Parsimon}\xspace/C    & 1m 19s      & $492\times$  \\
        \texttt{Parsimon}\xspace/inf  & 21s         & $1864\times$ \\
        \bottomrule
    \end{tabular}
    \caption{\small
        Running times and speed-up of \texttt{Parsimon}\xspace variants for five seconds of
        simulated time on a large oversubscribed network with thousands of
        hosts.
       
        We find that \texttt{Parsimon}\xspace estimates latencies orders of magnitude faster than
        does ns-3.
        %
        If there is ample opportunity for clustering or if there are infinite
        compute resources, speed-up is substantially further increased.
        %
        Measurements were taken on a 32-core machine.
    }
    \label{tab:large-scale}
    \vspace{-8mm}
\end{table}

Here we evaluate \texttt{Parsimon}\xspace's accuracy and performance on a 384-rack, 6144-host
topology.
The topology has eight pods, 48 racks per pod, and 16 hosts per rack, with
2-to-1 oversubscription.
For the workload, we use matrix B, the WebServer flow size distribution, and
high burstiness ($\sigma=2$).
We set a maximum link load of about 50\%, which gives the 100 most loaded links
an average load of 32\%, and the top 10\% most loaded links an average load of
about 15\%.
We configure all simulations to run for five seconds of simulated time.
To establish a baseline, we first run the scenario in ns-3, then we run the
scenario in \texttt{Parsimon}\xspace and \texttt{Parsimon}\xspace/C (see \Tab{variants}).
Due to memory constraints we omit \texttt{Parsimon}\xspace/ns-3 here, but we
include its analysis at smaller scale in \Sec{sensitivity}.

\Fig{large-scale} shows the accuracy of \texttt{Parsimon}\xspace relative to ns-3 across four flow
size bins.
We find that across all bins, both variants accurately estimate tail latencies.
If we consider all flow sizes together, we find that \texttt{Parsimon}\xspace and \texttt{Parsimon}\xspace/C overestimate
the p99 FCT slowdown by 8.8\% and 7.5\%, respectively.

\Tab{large-scale} shows the running time and speed-up for each estimator.
While ns-3 took nearly 11 hours, \texttt{Parsimon}\xspace without clustering took four
minutes and 13 seconds, for a speed-up of $154\times$.
If we turn clustering on by using \texttt{Parsimon}\xspace/C, the running time is further reduced
to one minute and 19 seconds, for a speed-up of $492\times$.
\footnote {
    We advise caution both in interpreting this number and in generalizing it
    to scenarios at large.
    %
    While our workloads are modeled after industry data, they are still
    synthetic.
    %
    There may be more or less opportunity to cluster and prune link-level
    simulations, depending on the structure of real workloads and the quality
    of the clustering algorithm.
}
In this case, only 25\% of links were simulated; the rest were pruned.
Lastly, \texttt{Parsimon}\xspace/inf estimates \texttt{Parsimon}\xspace's best possible performance given infinite
compute resources.
The longest-running single-link simulation took 11 seconds, and with the
additional 10 seconds required for network setup and convolution sampling, the
fastest projected running time is 21 seconds.

We chose an oversubscribed topology to slightly disadvantage \texttt{Parsimon}\xspace's method, as
oversubscription can lower \texttt{Parsimon}\xspace's accuracy.
\Sec{sensitivity} analyzes the effect of oversubscription in more detail.
We also ran the above experiment on a topology without oversubscription,
which for the same maximum load setting increased the top 10\% average link
load from 15\% to 25\%.
We found \texttt{Parsimon}\xspace's p99 accuracy improved from 9\% to about 7\%, while \texttt{Parsimon}\xspace/C's
accuracy remained approximately the same.
However, because aggregate load increased, ns-3 took 27 hours for five seconds
of simulated time, and speed-ups for \texttt{Parsimon}\xspace, \texttt{Parsimon}\xspace/C and \texttt{Parsimon}\xspace/inf were
$152\times$, $872\times$, and $3487\times$, respectively.
\texttt{Parsimon}\xspace/C benefited from the increased number of links in each ECMP grouping,
allowing it to prune 85\% of the link-level simulations.

\subsection{Sensitivity Analysis at Small Scale} \label{s:sensitivity}

\begin{table}
    \small
    \centering
    \begin{tabular}{p{3.2cm}l}
        \toprule
        Parameter              & Sample space                            \\
        \midrule
        Oversubscription       & 1-to-1, 2-to-1, 4-to-1                  \\
        Traffic matrix         & Matrix A, Matrix B, Matrix C            \\
        Flow size distribution & CacheFollower, WebServer, Hadoop        \\
        Burstiness             & Low ($\sigma = 1$), High ($\sigma = 2$) \\
        Max load               & 26\% to 83\% (continuous range)         \\
        \bottomrule
    \end{tabular}
    \caption{\small
        The sample space for the sensitivity analysis in \Sec{sensitivity}.
    }
    \label{tab:sample-space}
    \vspace{-3mm}
\end{table}

\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{figs/error-dist-0.pdf}
    \vspace{-6mm}
    \caption{\small
        CDFs of p99 error between \texttt{Parsimon}\xspace and ns-3 across all scenarios drawn from
        the sample space in \Tab{sample-space}.
        %
        The distributions are binned by maximum load.
        %
        In parentheses, we give the maximum value for the top 10\% average load
        in each bin.
        %
        Under common conditions of low to moderate load, \texttt{Parsimon}\xspace's estimates for
        the p99 FCT slowdown are reliably within 10\% of the ground truth.
    }
    \label{fig:error-dist-0}
\end{figure}

\begin{figure*}[t]
    \centering
    \begin{subfigure}[t]{0.45\linewidth}
        \centering
        \includegraphics[width=\textwidth]{figs/error-dist-1.pdf}
        \vspace{-5mm}
        \caption{\small
            Max load $\leq$ 50\%
        }
        \label{fig:error-dist-1}
    \end{subfigure}
    \hfill
    \begin{subfigure}[t]{0.45\linewidth}
        \centering
        \includegraphics[width=\textwidth]{figs/error-dist-2.pdf}
        \vspace{-5mm}
        \caption{\small
            Max load $>$ 50\%
        }
        \label{fig:error-dist-2}
    \end{subfigure}
    \vspace{-3mm}
    \caption{\small
        Distributions of p99 error between \texttt{Parsimon}\xspace and ns-3, faceted by different
        workload and topology parameters.
        %
        For each distribution we show the median, the quartiles, and a rotated
        kernel density estimation.
        %
        We consider the low-load regime (\Fig{error-dist-1}) and the high-load
        regime (\Fig{error-dist-2}) separately.
        %
        At low load, the workload and topology parameters only have a modest
        effect on \texttt{Parsimon}\xspace's accuracy, but at high load, the conditions leading to
        the largest errors come into view: high load, high oversubscription,
        with very short flows.
        %
        Note the different y-axes between the two load regimes.
    }
    \label{fig:other-variables}
    \vspace{-2mm}
\end{figure*}

\begin{table}
    \small
    \centering
    \begin{tabular}{rrcllr}
        \toprule
        Error  & Max load & Matrix & Sizes     & Oversub & $\sigma$ \\
        \midrule
        51.9\% & 77.6\%   & A      & WebServer & 4-to-1  & 1        \\
        30.1\% & 67.3\%   & A      & WebServer & 4-to-1  & 2        \\
        29.6\% & 67.0\%   & A      & WebServer & 4-to-1  & 2        \\
        25.6\% & 65.9\%   & A      & WebServer & 4-to-1  & 1        \\
        24.6\% & 73.2\%   & B      & WebServer & 4-to-1  & 1        \\
        \bottomrule
    \end{tabular}
    \caption{\small
        The five scenarios with the highest error values from the sensitivity
        analysis in \Sec{sensitivity}.
    }
    \label{tab:top5-error}
    \vspace{-6mm}
\end{table}

\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{figs/one-scenario.pdf}
    \vspace{-6mm}
    \caption{\small
        CDFs of FCT slowdown estimated by ns-3 and \texttt{Parsimon}\xspace for the scenario whose
        error is at the 85\textsuperscript{th} percentile of the p99 error
        distribution.
        %
        Note the y-axis.
        %
        Even though the accuracy here is worse than in the common case, \texttt{Parsimon}\xspace's
        estimates remain close across most of the tail.
        %
        Also shown is \texttt{Parsimon}\xspace/ns-3.
    }
    \label{fig:one-scenario}
    \vspace{-3mm}
\end{figure}

Next we turn our attention to how different aspects of workloads and
topologies affect \texttt{Parsimon}\xspace's accuracy.
To be able to simulate enough scenarios in ns-3 for a sensitivity analysis, we
downsample the topologies and traffic matrices to 32 racks.
The resulting topologies have two pods, 16 racks per pod, and eight hosts per
rack, and the number of spines per plane varies to accommodate different
oversubscription factors.

Our approach is as follows.
First, we construct a sample space over the parameters defining the workload
and the topology (aside from the number of servers, which is fixed).
The sample space is shown in \Tab{sample-space}.
Then, we sample 192 scenarios uniformly at random, and we run ns-3 and the
default \texttt{Parsimon}\xspace variant on each of them for several seconds of simulated time.
Next, for each scenario, we take the p99 FCT slowdown estimated by both ns-3
and \texttt{Parsimon}\xspace, and we compute the error between them.
If these values are $n$ and $p$ respectively, then the error is $(p - n) / n$.
Negative values indicate that \texttt{Parsimon}\xspace produced an underestimate.

Since we have one error value per scenario, the errors give rise to
distributions of error associated with the original sample space.
Now what remains is to determine how the workload and topology parameters
affect error distributions.
To start, recall from the discussion in \Sec{error-sources} that the magnitude
of error is expected to be load-dependent, with higher errors typically
manifesting at higher loads, so we begin by examining the effect of the maximum
load setting on \texttt{Parsimon}\xspace's accuracy.

\Para{Maximum load.} \Fig{error-dist-0} shows the error distributions binned by
maximum load.
Among all scenarios, \texttt{Parsimon}\xspace's p99 estimates are within 10\% of ns-3's estimates
85\% of the time
At high load, we observe larger overestimates of up to 52\% in the worst case.
In the most highly-loaded group of scenarios---with maximum link loads
between 56\% and 83\%---\texttt{Parsimon}\xspace is within 10\% of ns-3 62\% of the time, with an
average error of about 11\%.
However, this includes scenarios where 10\% of the links have an average load
of up to 68\%, which is much higher than what is reported in the literature.
For example, Roy {\em et al.}\xspace report that in Meta's data center network, 99\% of host
links are less than 10\% loaded, and the top 5\% of core links have loads
between 23\% and 46\%~\cite{fb-network}.
Among scenarios where the maximum link load is between 26\% and 41\%, \texttt{Parsimon}\xspace is
within 10\% of ns-3 100\% of the time.
If we further include scenarios with maximum link loads between 41\% and 56\%,
that number falls to 96\%.
Finally, while \texttt{Parsimon}\xspace's techniques tend to overestimate latencies, in
3\% of the scenarios, \texttt{Parsimon}\xspace underestimates p99 slowdown by up to 2\%.

\Para{Other parameters.} We next turn to the effects of all other workload and
topology parameters.
We start by only considering scenarios where the maximum link load is less than
or equal to 50\%; this will tell us whether any of the parameters have a large
effect on accuracy in the low-load regime.
\Fig{error-dist-1} shows the median error and error distributions as a violin plot for low-load scenarios grouped
by traffic matrix, flow size distribution, oversubscription, and burstiness.
Overall, changes to these parameters appear only to have a modest effect.
The choice of traffic matrix has the clearest trend, but load is a confounder
here: recall from \Fig{link-loads} that different traffic matrices yield
different link load distributions for the same maximum load setting.

When we look at the high load regime in \Fig{error-dist-2}, a clear picture
comes into view.
We see much longer tails in error distributions for matrix A, the WebServer
flow size distribution, and 4-to-1 oversubscription.
Together with \Fig{error-dist-1}, this suggests that none of these settings has
a strong effect on its own, but \emph{coupled together in the high load
    regime,} they have a pronounced effect on \texttt{Parsimon}\xspace's accuracy.
Matrix A induces higher average load and has more cross-rack traffic, making it
more likely for its flows to encounter multiple simultaneous bottlenecks.
The WebServer flow size distribution is dominated by short
flows (\Fig{flow-sizes}), a third of which are smaller than 1 KB and 80\% of
which are smaller than 10 KB. Because more of the traffic completes within
a single round trip, there is more ephemeral congestion and bandwidth smoothing
can have a larger impact.

Finally, oversubscription has an effect at high load: if
we removed all scenarios with 4-to-1 oversubscription, the maximum error would
only be 20\% rather than 52\%, even at high load.
In addition to the double counting of delays described in \Sec{error-sources},
oversubscription can also increase correlations in link delays.
To achieve 4-to-1 oversubscription in topologies as small as these, there are
only four spine switches per plane forwarding traffic between groups of 16
racks, leaving relatively few paths through the core.
Fewer paths can result in higher degrees of correlation---especially with matrix
A, whose traffic is primarily inter-rack (\Fig{matrices}).
Finally, this setting combined with the short flows from the WebServer
distributions gives rise to errors of up to 52\%.

\Tab{top5-error} lists the scenarios with the top five highest error values.
Four have matrix A, all have the WebServer distribution, and all five have
4-to-1 oversubscription.
In this group, the average maximum load is 70.2\%.
In practice, we believe it is rare to find all-to-all workloads on heavily
oversubscribed topologies where core links are persistently 70\% utilized.
Consequently, the data suggest that \texttt{Parsimon}\xspace maintains good accuracy under common
conditions.

\Para{Analyzing one scenario.} Finally, we pick one scenario to analyze so that we
can see the error of the entire tail rather than just the p99.
To pick one whose accuracy is worse than the average case, we rank-order all
scenarios by error and select the one at the 85\textsuperscript{th} percentile.
We find that it has matrix A, the Hadoop flow size distribution, low
burstiness, 2-to-1 oversubscription, and a maximum load of 68\% (with a top
10\% average load of 56\%).

\Fig{one-scenario} shows that accuracy at the p99 generalizes to other
percentiles in the tail.
We also run the scenario in \texttt{Parsimon}\xspace/C and \texttt{Parsimon}\xspace/ns-3 (\Tab{variants}), and we find
little accuracy difference between any of the variants.
For 14 seconds of simulated time, ns-3 took nearly five hours, \texttt{Parsimon}\xspace/ns-3
took 34 minutes, \texttt{Parsimon}\xspace took 1.5 minutes, and \texttt{Parsimon}\xspace/C took 49 seconds.
The speed-up of \texttt{Parsimon}\xspace/ns-3 being modest (see \Sec{fast-sim} for discussion), it
may appear at first glance as though most of \texttt{Parsimon}\xspace's benefit comes from the
custom backend.
However, gains due to the custom backend are fixed at an order of magnitude,
while gains due to decomposition scale with the number of cores and the size of
the simulated network.
In addition, decomposition is what enables other optimizations like clustering.

\section{Introduction}


Counterfactual simulation---to answer ``what if'' questions about the interaction
of network protocols, workloads, topology, and switch behavior---has long been
used by both researchers and practitioners as a way of quantifying the effect of design
options and operational parameters~\cite{sim97,ns-3,omnet,opnet,dctcp,dcqcn,homa,hpcc}.
As production data center networks have scaled up in bandwidth and
scaled out in size~\cite{fb-fabric,jupiter}, however, network simulation has failed to keep pace.  Although
there is ample parallelism at a physical level in large scale data center networks, it has been
difficult to realize significant speedup with packet-level network simulation~\cite{parsim94,genesis}.
As packets flow through the network, the scheduling decisions at each switch affect the behavior
of every flow traversing that switch, and therefore the scheduling
decisions at every downstream switch, and---with congestion control---future flow behavior,
in a cascading web of very fine-grained interaction.
In our own experiments using ns-3~\cite{ns-3}, for example,
simulating a 384-rack, 6,144-host network on a standard
multicore server took 11 to 27 hours of wall-clock time to advance five seconds of simulated time.
As a result, packet-level network simulation today is mostly used for small scale studies.

\if 0
    Flow-level network simulation, where flows are modelled
    as fluids flowing smoothly through a series of network bottlenecks,
    offers one possible avenue for simulation speedup. However, this comes at considerable
    loss in accuracy~\cite{mimicnet} for modest gain.  Data center networks today serve
    workloads dominated by episodic bursts of small remote procedure call requests,
    rather than very long-running data transfers.  With link speeds of 100 to 400\,Gbps, most
    data center network flows are much shorter than the bandwidth delay product~\cite{homa},
    limiting speedup.
\fi

In recent work, MimicNet proposes an alternative approach, using machine learning to construct
a model of how different parts of the network affect other parts of the network~\cite{mimicnet}.
Although promising, MimicNet has significant limitations.
Because it uses packet-level simulation to train the model, MimicNet can take several hours to train on a new
workload or network configuration, limiting its utility for exploring a wide design space.
Further, since MimicNet scales by replicating a model trained on a portion of the network, it is
limited to failure-free uniform fat trees with uniform traffic among equally sized clusters.
Of course, production networks typically run a diversity of workloads
and suffer frequent partial or grey failures that result in
asymmetric topologies and performance~\cite{corropt}.
Sensitivity of network performance during failure episodes is important to network operators~\cite{f10,mogul-nines}.
Another operational use case is to predict the impact of planned partial network outages and incremental network upgrades on
application performance~\cite{andromeda,patchpanel}.

This paper aims to address this gap, to develop techniques for fast
simulation of large scale networks with arbitrary workloads and topologies.
Our work involves no training step, aiming to produce near-real time results.
A key observation is that we could achieve high degrees of parallelism if we could somehow
disentangle the interactions between switch queues, allowing us to study the behavior of the traffic
on each link in isolation. Of course, switch queues are not in reality completely disentangled.
The packets for any particular flow experiences a very specific set of conditions at each switch,
and those conditions are affected by the presence of upstream bottlenecks which
can smooth packet arrivals for competing flows at downstream switches.  The congestion response
for a flow depends on the combination of conditions at every switch along the path.

However, large scale data center networks are typically managed with the goal of delivering consistent
high performance to applications. While congestion events do occur, they are often chaotic rather
than persistent, popping up and then disappearing in different spots due to the inherent
burstiness and flow size distribution of applications, rather than due to some long-term
mismatch between demand and capacity in some portion of the network.  Further, we are often
interested in aggregate behavior, such as the frequency of poor flow performance, rather than
accurately modeling the behavior of each individual packet or flow.

Thus, our hypothesis is that we can approximate the distribution of end-to-end flow performance
for a particular workload running on a large scale network by modeling
the frequency and magnitude of local congestion events at each link along the path.
A long flow will of course experience multiple congestion events during its lifetime,
but most of these will occur at different points along the path {\em at different times}. 
Modeling the effect of simultaneous congestion events, and the response of the congestion
algorithm to multiple simultaneous bottlenecks, is second order. 

Our hypothesis is related to the concept of product-form solutions in queuing theory. For certain classes of queueing networks (e.g., Jackson~\cite{jackson1957networks} and BCMP networks~\cite{baskett1975open}), the equilibrium distribution of queue lengths can be written in product form, i.e., the state of an individual queue is only dependent on the traffic it receives
and not on the state of the rest of the network. These results generally require specific assumptions about job arrival processes (e.g., Poisson), service-time distributions (e.g., exponential), and queueing/routing disciplines (e.g., FIFO or processor-sharing queues), and there has been much theoretical work on identifying classes of queueing networks that admit product-form solutions~\cite{kelly1976networks}. Although data center networks do not strictly conform to these conditions and the dynamics of each individual queue can be quite complex (e.g., due to
congestion control), our hypothesis is that product-form solutions are approximately true in most realistic settings, and therefore 
we can analyze individual queues in isolation and combine the results to approximate end-to-end network behavior.

\begin{figure}[t]
    \centering
   
    \includegraphics[width=\linewidth]{figs/banner.pdf}
    \vspace{-7mm}
    \caption{\small
        CDF of ns-3 versus \texttt{Parsimon}\xspace for flow completion time (FCT) slowdown across
        multiple flow size ranges, zoomed into the tail.
        %
        While ns-3 took nearly 11 hours to produce these results, \texttt{Parsimon}\xspace took one
        minute and 19 seconds, end-to-end.
        %
        Results were taken on a 6,144-host topology with an industry traffic
        matrix, 2-to-1 oversubscription, and bursty traffic.
    }
    \vspace{-4mm}
    \label{fig:banner}
\end{figure}

We built \texttt{Parsimon}\xspace to directly test this hypothesis.  First, we deconstruct the network topology
into a large number of simple and fast simulations where each can be run entirely in parallel by
a single hyperthread.
Each simulation aims to collect the distribution of delays that flows of a particular size
would experience through a single link, assuming that the rest of the network
was benign. We then combine these simulated delay distributions to produce predictions of
the end-to-end delay distribution, again for flows of a given size.
At each step, we make conservative assumptions for how delays should be computed and combined,
and thus our work provides a bound on the distribution of flow performance.
In many settings, researchers and operators are interested in guaranteeing
that tail behavior is well-managed, making a conservative assumption more appropriate than an optimistic one.
Finally, \texttt{Parsimon}\xspace clusters links with common traffic characteristics, eliminating much of the overhead
of simulating parallel links in the core of the network as well as edge links used by replicated
or parallel applications, further improving simulation performance.

Because validation against detailed packet-level simulation at scale is so expensive,
we limit our study to a single widely used transport protocol, DCTCP~\cite{dctcp}, with FIFO queues
with ECN packet marking at each switch~\cite{ecn}.
We also focus on queue dynamics rather than packet loss; most data center networks are provisioned
and engineered for extremely low packet loss~\cite{fb-network,jupiter}.
We note that these assumptions are not fundamental to our approach, but validation of other transport
protocols~\cite{hull,homa,hpcc,swift}, switch queueing disciplines~\cite{wfq,spfifo,homa,bfc}, and packet loss
remains future work.
We note that modern data center transport layer protocols like DCTCP are adept at quickly adapting to the presence
and absence of congestion, and so we caution our results may not extend to older transport protocols
where convergence time is a large factor.

\Fig{banner} shows a sample of our results for the 6,144 host network mentioned above,
running a published industry traffic matrix~\cite{fb-network} and flow size distribution~\cite{homa},
and with standard settings for burstiness and over-provisioning.  We describe the details of this and other
experiments later in the paper. Depicted are distributions of flow completion time (FCT) slowdown (the ratio
to the time the flow would take on an otherwise unloaded network), binned by flow size.
While ns-3 took nearly 11 hours on this configuration, \texttt{Parsimon}\xspace was able to match flow-size specific performance of ns-3 
in 79 seconds (a 492 times speedup) on a single 32-way multicore server with an error
of 9\% at the 99th percentile.
Given a small cluster of simulation servers, we estimate a completion time of 21 seconds using our approach.

In our evaluation, we scan the parameter space to identify circumstances where our approximations are
less accurate.  Link clustering improves performance but hurts accuracy somewhat; this tradeoff can be avoided by using more simulation cores.
Without clustering, accuracy suffers when there is high utilization of links in the core (above 50\%),
there are high levels of overprovisioning, and a large fraction of network traffic
is due to flows that finish within a single round trip.
Generally, a combination of factors is required for poor accuracy.
In 85\% of the configurations we test, the error relative to ns-3 is under
10\%. We note that MimicNet reports a mean error rate of 5\%. However, they
test configurations with 100 Mbps links instead of the 10 Gbps and 40 Gbps
links we assume, with the result that much less of their traffic is due to
flows that finish within a single round trip.

\if 0
    Many cloud applications are tail latency sensitive, with end-to-end performance that depends on
    factors both within the customer's control, such as burstiness and flow lengths, as well as
    outside factors, such as oversubscription, network failures, and competing traffic.
    To deliver consistently good performance, cloud network operators often need to answer
    ``what if'' questions about the tail latency performance of their networks.
    For example, what will be the impact of the launch of a new viral application, such as Pokemon Go,
    on network performance for unrelated cloud customers? What is the expected impact on customer
    performance of aggregation or core switch failures, or a partial power outage?  Do individual
    virtual customer networks experience atypical network latencies? What is the impact of potential
    changes to class-based scheduling and prioritization?

    (kevin's original)

    In data center networks, fast and accurate tail latency estimates offer a
    strong basis for providing responsiveness guarantees.
    %
    With a good estimation procedure, an operator should be able to quickly assess
    the latency impacts of a broad array of scenarios---from workload shifts, to
    capacity scaling, to link failures, and more---so that appropriate actions can
    be taken to maintain a target responsiveness or better utilize the network.

    Ideally, such a procedure would consider the network at scale and complete
    quickly enough to permit continuous and iterative what-if analysis.
    %
    Unfortunately, the sheer size of today's data center networks---with nodes
    numbering in the hundreds of thousands~\cite{fb-network}---leaves existing
    methods ill-suited to the task.
    %
    For example, full-scale hardware testbeds can achieve maximal realism but bear
    prohibitive cost for large networks.
    %
    On the other hand, small-scale hardware or emulated testbeds\todo{cites} are
    cost effective but trade the ability to capture consequential effects arising
    from the whole topology and its workload.
    %
    An alternative to testbeds small or large is to use the production network
    itself, dividing it into logical slices for A/B testing~\todo{cites}, but this
    is more suitable for assessing correctness at scale rather than performance, as
    performance can easily be degraded.

    Finally, there is simulation.
    %
    At first glance, simulation appears promising: it trades hardware realism for
    low cost and--in principle--infinite scale, allowing operators to focus
    separately on important determiners of network tail latency like queueing,
    congestion control, topologies, and workloads.
    %
    However, it is well known that full-fidelity simulations have completion times
    that scale poorly with network size.
    %
    In our own measurements, simulating an 384-rack, 6,144-host network took over 27
    hours of wall-clock time to advance five seconds of simulated time---an onerous
    inflation of $19,000-20,000\times$.

    Recent work has noted that accuracy is often at odds with speed---especially
    when networks are large---and has shown that it is possible to occupy a
    desirable point in the accuracy and speed trade-off space with the aid of
    machine learning, but only so long as certain conditions are
    met~\cite{mimicnet}.
    %
    These conditions include full-bisection-bandwidth fat trees, last-hop dominated
    congestion, and uniform traffic among equally-sized groups of
    nodes~\cite{mimicnet}.
    %
    These restrictions are appropriate for many kinds of protocol and architecture
    evaluation; however, they are not suitable for tail latency estimation with
    realistic topologies---which are often oversubscribed---and realistic
    workloads---which are rarely uniform among all clusters of nodes.
    %
    This raises the question of whether it is possible for simulation to estimate
    tail latencies 1) at high speed 2) with good accuracy 3) and on realistic
    topologies and workloads.

    We show these goals can be met with \texttt{Parsimon}\xspace, a fast estimator for  tail latencies
    in data center networks.
    %
    \texttt{Parsimon}\xspace is designed to impose few restrictions, and its goal is to help operators
    set and maintain service-level objectives~\cite{mogul-nines} (SLOs) for flow
    completion times (FCTs).
    %
    In this paper we phrase SLOs as bounds on the tail of FCT slowdown
    distributions, where FCT slowdown (henceforth "slowdown") is the measured FCT
    divided by the ideal FCT on an unloaded network.
    %
    An operator might set an SLO stating, as an example, that the
    99\textsuperscript{th} percentile (henceforth "p99") slowdown should not exceed
    a factor of five.

    At \texttt{Parsimon}\xspace's core is a set of approximation techniques designed to trade small
    amounts of accuracy for large gains in simulation speed.
    %
    Because \texttt{Parsimon}\xspace is intended to help manage SLOs, its key approximations are
    \emph{biased toward overestimation}: we want to minimize the chance that an SLO
    is missed, but we still want to set tight bounds.

    The first and most aggressive approximation enables the wholesale
    parallelization of a network simulation.
    %
    For each link, \texttt{Parsimon}\xspace generates a small backend topology and simulation that aims
    to capture the effect of just that link on end-to-end FCT distributions.
    %
    All of these link-level simulations are independent and can therefore be
    executed in parallel, and their results are later aggregated to support
    full-network predictions.
    %
    A primary contribution of this work is a discussion of how to generate the
    link-level simulations and aggregate their results in a way that preserves good
    accuracy.
    %
    We also discuss the rare scenarios in which the approximation can produce large
    overestimates.

    The chief benefit of decomposing the network is parallelization: in the limit,
    each link is simulated on a separate core, and simulation times always scale
    with network sizes, provided there is enough compute.
    %
    However, there are additional benefits.
    %
    First, the link-level simulations become simple enough to model and optimize
    with ease.
    %
    In our experiments we find they can be sped up by an order of magnitude with
    negligible loss of accuracy.
    %
    In addition, symmetries present in data center topologies and workloads result
    in redundant link-level simulations that can be clustered and pruned, yielding
    further substantial improvements in simulation time and/or resource
    requirements.

    Altogether, \texttt{Parsimon}\xspace's techniques maintain good accuracy while accelerating large
    simulations by multiple orders of magnitude.
    %
    As an early example, \Fig{banner} shows \texttt{Parsimon}\xspace's accuracy on a topology and
    workload extracted from a public industry dataset~\cite{fb-network}.
    %
    Depicted are distributions of FCT slowdown binned by flow size.
    %
    For a ground-truth comparison, we use ns-3~\cite{ns-3}, a discrete event
    simulator in wide use among the networking community.
    %
    Across all flow size bins, we find that \texttt{Parsimon}\xspace estimates tight bounds for the
    ground truth, and it does so at a speed-up of $585\times$.
    \kz{number subject to change}

    To summarize, this paper contributes methods to drastically accelerate data
    center network simulation for estimating tail latency SLOs.
    %
    We implement the techniques in a prototype called \texttt{Parsimon}\xspace, and in extensive
    evaluations with multiple topology sizes, oversubscription factors, flow size
    distributions, burstiness amounts, load levels, and industry traffic matrices,
    we find~\kz{blah blah blah once it's all settled}.
\fi

\section{Key Methods: Decompose and Aggregate} \label{s:key-methods}

\begin{figure*}[t]
    \centering
    \includegraphics[width=\linewidth]{figs/link-level.pdf}
    \vspace{-6mm}
    \caption{\small
        An illustration of how \texttt{Parsimon}\xspace generates link-level topologies.
        %
        Simulations are unidirectional, and a different topology is used for (A) first-hop links,
        (B) switch-to-switch links, and (C) last-hop links.
        For illustration purposes, each link in the original topology has a propagation delay of one.
        %
        To the left is the original topology; to the right are the corresponding link-level topologies,
        with new propagation delays annotated. Bold lines denote links whose bandwidths have been artificially
        increased during topology generation.
       
    }
    \label{fig:link-level}
    \vspace{-2mm}
\end{figure*}


Together, the methods for decomposition and aggregation are what enables \texttt{Parsimon}\xspace's
scaling, and while we later engage additional techniques for further
speed-up, they are a byproduct of---and not independent from---these more
essential methods.
Decisions made during this step are also the central determiners of accuracy.
This section describes these processes in detail: how link-level topologies are
generated, how the link-level data are post-processed and stored, and finally
how they are aggregated to produce end-to-end estimates.

\subsection{Generating Link-Level Workloads} \label{s:link-workloads}

To start, \texttt{Parsimon}\xspace associates each link with the flows passing through it.
Since links are bidirectional, there are two sets of flows---and consequently
two link-level simulations---per link.
\texttt{Parsimon}\xspace populates links with flows using flows' routes.
Then for each link and in each direction, the associated flows constitute the
input workload to the link-level simulation.
The sizes and arrival times of the flows pass though unmodified.

\subsection{Generating Link-Level Topologies} \label{s:link-topos}

Once the link-level workloads are in place, we generate the link-level
topologies.
In this step, we think of each link as contributing some amount of delay to
end-to-end FCTs.
Any given flow will accrue these delays at each hop, depending on---for
example---how much bandwidth is available and how much queueing is present.
Highly-loaded links are expected to contribute more delay, while rarely
utilized links will contribute relatively little.

For each link and in each direction, we generate a topology and perform a
simulation using just the flows traversing that link.
Once the simulation is finished, the delay caused by the link for a given flow
is computed by taking the observed
FCT and removing the ideal FCT for that flow size.
(For a flow of size $s$ traversing a link of speed $C$ and propagation delay $l$,
the ideal FCT is $s/C + l$.)
This intuitively captures all delays incurred due to queueing,
congestion control, bandwidth sharing, and so on at the target link.

In generating a per-link topology, our goal is to isolate and measure the expected delay
contribution of the target link. A simple but inefficient strategy would
be to use the original
topology, but with only the traffic traversing the target link, without any
cross traffic.  This would be relatively accurate
at measuring the delay contributed by the target link, albeit a bit conservative.
Upstream cross traffic congestion will slightly smooth out downstream
congestion at the target link, and so removing cross traffic would make the
queue distribution at the target link slightly worse than in reality.

Although relatively accurate and parallelizable, simulating every link on the original network
topology would still be inefficient, as packet-level simulation cost is roughly proportional to the
number of packets simulated times the number of hops each packet takes through the network.
Because we run the link simulation separately in each direction on every packet that passes through that link,
this would inflate the aggregate computational cost of the simulation
by a multiplicative factor of roughly half the average network path length---a significant factor for large-scale networks.
Instead, we want to simulate only a small constant number of hops per target link.

An extreme alternative would be to simulate only the target switch queue.
This is inaccurate for two reasons.  First, we need to preserve
end-to-end round trip delays, as these affect the speed of the congestion control
adaptation to congestion or its absence; hosts closer to the target adapt faster than those
farther away.  Second, we need to preserve the
spacing of packets induced by the original topology---a large flow does not immediately dump
all of its data into the queue for the target link; instead, those packets arrive
spaced apart by the edge link capacity. Ignoring this effect would lead to larger
queues and more delay at the simulated link than would occur at that link in the original network.


\if 0
    \texttt{Parsimon}\xspace is agnostic to the particular simulation backend used at the link-level.
    It only assumes that the backend can 1) take a topology and a list of flows and
    2) estimate an FCT for each flow.
    %
    It is therefore up to the topology generator to ensure that most of the
    measured delay is due to the target link.
    %
    In addition, it helps for backend topologies to be small so they can be further
    modeled and optimized (\Sec{fast-sim}), but to maintain accuracy they must also
    preserve certain features of the original network.
    %
    In what follows we discuss which choices we have found most profitable.

    Throughout, we will refer to \Fig{link-level}, which shows the process by way
    of a simple example.

    \Para{Minimizing the number of hops.} For networks, the speed of discrete event
    simulation is mainly determined by 1) the number of packets simulated and 2)
    the number of events generated per-packet.
    %
    In most cases, the fraction of total traffic routed through a particular link
    will be small, and this is what lends the link-level simulation most of its
    speed advantage.
    %
    However, for additional speed-up we can also decrease the total number of
    events per-packet by minimizing the number of hops from sources to
    destinations.
    %
    Doing so also has the key benefit of producing simulations that can be highly
    optimized; we discuss this in \Sec{fast-sim}.
\fi

Thus, we construct a topology for each link-level simulation that reflects a performance-accuracy
tradeoff, attempting to capture the most important effects for computing the delay contributed by
the target link.
\Fig{link-level} shows how topologies are minimized.
The generated topology takes one of three shapes, depending on the location and direction
of the target link: (i) a first-hop up-link from a host to a ToR, (ii) a switch-to-switch link in the middle of the network, or (iii) a last-hop downlink from a ToR to a host.




Suppose the traffic through the target link
originates from sources $S$ and terminates in destinations $T$.
In case \texttt{A} of \Fig{link-level}, we connect the target link directly to each
host in $T$ via a dedicated link.
If the target link is a switch-to-switch link (case \texttt{B}), we remove intermediate hops and connect
the hosts in $S$ directly to the input, and the output directly to the hosts in $T$.
Lastly, if the target link is a last hop (case \texttt{C}), then the
hosts in $S$ are connected directly to the input.
Rewriting the topology in this manner ensures that packets can traverse at most
three hops, regardless of the size of the original topology.

\if 0
    \Para{Preserving sources and destinations.} For each link-level simulation, $S$
    and $T$ are inferred from the link-level workload.
    %
    Suppose $F$ is the link-level workload, and let $s$ and $t$ be functions that
    map a flow to its source and destination, respectively.
    %
    Then
    %
    \begin{equation*}
        S\ =\ \{\ s(x)\ |\ x \in F\ \}
        \qquad \text{and} \qquad
        T\ =\ \{\ t(x)\ |\ x \in F\ \}.
    \end{equation*}
    %
    As a reminder, our goal in generating a link-level simulation is to isolate the
    delay contribution of the target link.
    %
    Consequently, it may seem natural to include many more sources or destinations
    where possible.
    %
    For example, in cases \texttt{B} and \texttt{C} of \Fig{link-level}, \texttt{Parsimon}\xspace could
    in principle generate many more sources and rewrite the flows to be evenly
    distributed among them (subject to the other constraints we describe later).
    %
    Doing so would minimize the chance that any delay incurred during the
    simulation is due to first-hop links rather than the target link.
    %
    However, we have found that (further) inflating the fan-in to the target link
    results in much longer queue lengths in the tail of its queue length
    distribution, leading to large overestimates for the tail delay of short flows.
    %
    In practice, the delay contributed by the first-hop links in cases \texttt{B}
    and \texttt{C} of \Fig{link-level} is likely to be small, since only the flows
    passing through the target link are simulated.
\fi

\Para{Modeling round-trip delay.}
Next, we set the link delays in each constructed topology to match the round trip
delays in the original network.
For example, in case \texttt{A} of \Fig{link-level}, the round-trip time between host \texttt{0} and
host \texttt{2} is 8 in both the original topology and the
generated topology, even though \texttt{Parsimon}\xspace has removed intermediate hops between the
switch and host \texttt{2}. \Fig{link-level} is meant as illustrative;
as with ns-3, \texttt{Parsimon}\xspace can model arbitrary round-trip delays.

In data center networks, congestion controllers play a large role in
determining the extent to which longer flows yield throughput to benefit the
latency of short flows.
Most algorithms such as DCTCP~\cite{dctcp}, DCQCN~\cite{dcqcn}, and
TIMELY~\cite{timely} are \emph{end-to-end} in the sense that sources adjust
their sending rates based on feedback echoed from destinations~\cite{bfc}.
With an end-to-end control loop, a source
must wait an entire round-trip time (RTT) before being able to adapt its
sending rate based on congestion feedback, resulting in longer queue lengths
with higher RTTs. Thus, correctly modeling RTTs is essential to correctly modeling
queue dynamics.

\if 0
    Modeling round trip delays correctly is necessary to reflect the different
    performance experienced by different length flows.
    \Para{Preserving round-trip times.} When removing intermediate hops, we have found it necessary to preserve round-trip times between hosts.
    %
    If the RTT is long, large flows may send more data before being throttled,
    resulting in longer queue lengths.
    %
    Conversely if the RTT is short, large flows may be throttled immediately,
    prolonging their delays but keeping queues shorter.
    %
    Failure to adequately capture the RTTs between hosts can result in large errors
    in the tail of queue length distributions.
\fi

\Para{Selecting link bandwidths.}
In some cases, we
artificially increase the bandwidth of downstream links to ensure that
they do not artificially add congestion. We say such links are \emph{inflated}.
For example, in cases \texttt{A} and \texttt{B} of \Fig{link-level}, the
bandwidths of the last-hop links are inflated.
We want any queueing to be due to the target link and not the downstream link.
By inflating downstream links, we remove store and forward delay
(a small packet following a large packet
would otherwise need to queue for the downstream link); it also addresses the
case where core links are fatter than downstream links.
Queueing at the downstream link itself is accounted for in case \texttt{C}.
By contrast, we do {\em not} inflate first-hop links in cases
\texttt{B} and \texttt{C}, as this would enable a long flow to arrive at
the target link at a higher rate than it would in practice.

A cluster of sources sending simultaneously through an oversubscribed
top-of-rack (ToR) switch in the original network will be throttled beyond
what is implied by the edge link capacity.
To improve simulation speed, we ignore this effect and are therefore
slightly conservative in our estimates for oversubscribed networks.

\if 0
    If \texttt{Parsimon}\xspace were to inflate these links, then a long flow arriving at any source
    would be able to send far more data than would otherwise be possible before
    being throttled by the congestion controller.
    %
    This would once again produce errors in queue length distributions, resulting
    in large overestimates for delay.
    %
    For these links, \texttt{Parsimon}\xspace selects the minimum bandwidth between the hosts and the
    bottleneck, which, in practice, is usually the bandwidth of the first-hop link.
    %
    As previously discussed, delays due to first-hop links in cases \texttt{B} and
    \texttt{C} are likely to be small because the traffic is usually spread out
    among many sources.
\fi

\Para{Correcting for ACK traffic.} Since \texttt{Parsimon}\xspace only simulates one direction at a
time, we must account for the load induced by acknowledgments due to traffic
in the reverse direction.  This is usually small, but can be significant at high load
and where average packet size is small.  Instead of modeling ACK traffic in detail,
we apply a simple rule, mechanically reducing the forward bandwidth on each simulated
link by the average volume
consumed by ACKs for flows in the opposite direction over the course of the simulation.
This correction is applied to all links but is most necessary for the target
link.  Note that \texttt{Parsimon}\xspace does not account for extra delay caused by ACK jitter on the reverse path;
this could be an issue when applying our ideas to networks with bandwidth asymmetry between forward and reverse paths~\cite{reversepath}.

\if 0
    %
    The process is as follows.
    %
    When selecting a bandwidth for a link $l$, \texttt{Parsimon}\xspace inspects the link-level
    workload of the same link $\bar{l}$ going in the reverse direction.
    %
    Then, \texttt{Parsimon}\xspace estimates the ACK load induced by $\bar{l}$'s workload and uses it
    to slightly adjust $l$'s bandwidth.
\fi

\subsection{Post-Processing Link-Level Results} \label{s:post-processing}

Each link-level simulation produces an FCT for each flow in the link-level
workload, and these FCTs are used to compute delays.
Recall from \Sec{link-topos} that the delay is just the observed FCT minus the
ideal FCT on an unloaded network.  For each flow, we could, theoretically, estimate the end-to-end delay
as some function of the delay contributed by each link for that flow. We discuss how that function works
in \texttt{Parsimon}\xspace, along with its sources of bias, later in this section.

\if 0
    Of course, this estimate would be conservative (it would slightly overestimate the delay) for long flows.
    The delay for a flow of a few packets is well-modeled as the sum of the delay at each hop, but
    long flows that encounter simultaneous cross-traffic congestion at multiple points along the path
    during the same round trip will ``double count'' those delays -- the congestion control
    protocol will (generally) back off an amount appropriate for the most congested link rather
    than based on the sum of the simultaneous congestion.  We discuss this more below.
\fi

First, we address a different issue. Recall that we cluster similar links together (\Sec{clustering})
so that we only simulate the flows through a single representative link for each cluster of links.
Thus, to compute the end-to-end delay for a particular flow, we take a sample
from the delay distributions at each hop in the path, or from the hop's standin representative.

In post-processing the link-level results and constructing these distributions, our
primary objective is to support accurate estimates for \emph{all flow sizes.}
It is not enough to produce the correct FCT distribution across the
entire workload; we must also accurately estimate the FCT distribution for
short flows containing just a few packets as well as for long flows that last for
hundreds of round trips.
This extra requirement necessitates some post-processing before distributions
can be constructed.
Here we describe how this is done.

\Para{Packet-normalized delay.} Maintaining accuracy across all flow sizes
would not be possible if we used delays directly.
For example, long flows, which may experience variations in their bandwidth
share over time, will almost always experience more absolute
delay than short flows.

As a start, we can address this by normalizing delays by flow size: after
computing the delay for a particular flow, we can then divide the delay by the
flow's size in packets.
We call the resulting metric the \emph{packet-normalized delay}, and it has the
intuitive interpretation of summarizing the flow's average delay per packet.
Link-level distributions are constructed from packet-normalized delays rather
than absolute delays.
We normalize by the number of packets instead of the number of bytes because
flows are discretized into---and therefore delays are incurred by---packets.
Further, normalizing by the number of bytes loses accuracy for small flows,
especially those smaller than the maximum packet size. Both 50 and 100 byte
packets are equally delayed in the tail if they arrive in the switch queue behind a jumbo
(9 KB) packet~\cite{jumboframes}.

\Para{Bucketing distributions.} Even with packet-normalized delays, we should
still expect long flows to have different delay distributions than short flows.
The FCT of a long flow is mainly determined by the throughput it achieves,
while the FCT of a short flow depends on how much queueing it encounters.
Further, congestion control algorithms trade the throughput of long flows for
the latency of shorter ones to varying degree.
An aggressive congestion control algorithm could try to keep queues
near-empty~\cite{hpcc}, resulting in smaller short-flow delay and larger
long-flow delay.

To ensure that estimates for different flow sizes are accurate, it is necessary
to sample each packet-normalized delay from the appropriate distribution.
We bucket the distribution of packet-normalized delays by flow
size. Buckets need to contain enough samples to form statistically meaningful distributions, but
they should also be small enough so that the values come from
flows with similar delay characteristics ({i.e.},  similarly-sized flows).

\texttt{Parsimon}\xspace uses a simple bucketing algorithm.
In brief, we start with a packet-normalized delay per flow, and we sort them
according to flow size.
Then, starting with the shortest flow, we begin populating buckets.
For each bucket $b$, let $\text{maxf}_{b}$ and $\text{minf}_{b}$ be the maximum
and minimum flow sizes associated with $b$, respectively, and let $n_{b}$ be
the number of elements in $b$.
Each bucket $b$ apart from the last one is locally subject to two constraints
\vspace{-1mm}
\begin{equation*}
    n_{b} \geq B
    \qquad \text{and} \qquad
    \text{maxf}_{b} \geq x * \text{minf}_{b},
    \vspace{-1mm}
\end{equation*}
for some choice of $B$ and $x$.
Globally, \texttt{Parsimon}\xspace also ensures buckets are contiguous and non-overlapping.
For any bucket, once the two local constraints are satisfied, \texttt{Parsimon}\xspace begins
populating the next bucket, and the final bucket is assigned whatever elements
remain.

In practice, we find $B = 100$ and $x = 2$ works well.
Data center workloads have heavy-tailed flow size distributions in which short
flows arrive much more frequently than long ones.
With these parameters, the first buckets will have size boundaries that are
approximately powers of two, and as flows get larger, buckets will cover larger
and larger ranges.
This is the desired behavior.
Intuitively, a 1 KB flow should not be grouped with a 1 MB flow, but a 1 GB
flow can be safely grouped with a 10 GB flow because we expect them to have
similar delay contributors.

\vspace{4pt}

In summary, each link-level simulation produces FCTs, and these FCTs are used
to construct bucketed distributions of packet-normalized delay.
Since different links have different workloads, bucketing is performed on a
per-link basis.
This means that the links in any given path are likely to have different bucket
sizes with different flow size ranges.
In the next subsection (\Sec{aggregation}) we describe how the data are
aggregated.

\subsection{Aggregating Link-Level Estimates} \label{s:aggregation}

\begin{figure}[t]
    \centering
   
    \includegraphics[width=0.85\linewidth]{figs/aggregation.pdf}
    \vspace{-4mm}
    \caption{\small
        An illustration of how \texttt{Parsimon}\xspace aggregates link-level results into a
        path-level point estimate. \texttt{Parsimon}\xspace samples a packet-normalized
        delay (\Sec{post-processing}) from each link along the path, and
        combines these to estimate the end-to-end absolute delay $D$.
       
    }
    \vspace{-4mm}
    \label{fig:aggregation}
\end{figure}


For any given range of flow sizes, the final distribution of
(packet-normalized) delay for any path through the network can be estimated by
selecting an appropriate distribution from each component link and then
performing an n-ary convolution.
However, the efficiency of this step must be considered.
Since there are multiple distributions per link and potentially many paths
through the network, performing all convolutions up front and storing one
path-level distribution per path, per flow-size range would be costly in space
and in time.

To avoid these costs, \texttt{Parsimon}\xspace uses an on-demand sampling strategy to perform the
convolution.
Recall that the simulation step resulted in bucketed distributions of
packet-normalized delay per link, organized in a graph isomorphic to the
original topology.
\texttt{Parsimon}\xspace makes this graph a queryable object that is capable of supporting point
estimates.
Given a size, a source, and a destination, \texttt{Parsimon}\xspace computes a path from the source
to the destination and uses the size to select a distribution per-link.
Then, one packet-normalized delay is sampled from each distribution and the
results are subsequently combined into a point estimate.
Suppose there are $n$ hops and let $D^*_1, D^*_2, \ldots, D^*_n$ be the sampled
packet-normalized delays.
Then, the end-to-end absolute delay $D$ is computed as
\vspace{-1mm}
\begin{equation*}
    P \sum_{i=1}^{n} D^{*}_{i}
    \enspace = \enspace \sum_{i=1}^{n} D^{*}_{i}P
    \enspace = \enspace \sum_{i=1}^{n} D_{i}
    \enspace = \enspace D,
    \vspace{-1mm}
\end{equation*}
where $P$ is the input flow size in packets and $D_i$ is the absolute delay for
hop $i$.
\Fig{aggregation} illustrates this process.
Finally, to obtain a distribution of end-to-end delay estimates, we need only
sample enough point estimates for the desired flow size range and source
destination pairs.

\subsection{Primary Sources of Error} \label{s:error-sources}

To balance accuracy and performance, \texttt{Parsimon}\xspace makes a number
of approximations, with some having more of an effect on accuracy than
others.
Here we catalog some of the main sources of error, describing 1) how we expect
the errors to manifest and 2) what modifications, if any, could be made to address them.

\Para{Bottleneck fan-in.} To simulate a given target link in the network, \texttt{Parsimon}\xspace constructs a topology
that connects all of the source nodes feeding traffic directly into that target.
In practice, of course, there would be multiple stages of fan-in, and that fan-in would tend to
spread out any burst of arriving flows due to upstream bandwidth capacity constraints.
Any target
link would experience slightly less queueing and less congestion in reality than in \texttt{Parsimon}\xspace.
Of course, \texttt{Parsimon}\xspace also simulates the upstream link; because it is closer to the sources,
its traffic and queueing behavior would be a closer model to what would happen in a
full network-wide simulation.

Because \texttt{Parsimon}\xspace sums the delay contributed by each hop along a flow's path, the lack of
fan-in will tend to slightly overestimate the delays caused by downstream links.
Put another way, any delay induced by fan-in constraints is counted twice---once
when we simulate the upstream link and again when we simulate the downstream link.
In our evaluation, accuracy
is slightly lower for networks with higher degrees of oversubscription, as we would expect.
We could potentially remove this inaccuracy by including the upstream fan-in as part of the
topology for each link simulation. Since simulation time is proportional to the number of hops,
this would decrease individual link simulation efficiency by a small but significant factor.

\if 0
    Similarly, connecting sources directly to the target
    link artificially increases the link fan-in, which could result in more traffic
    arriving simultaneously at the target link than would otherwise be possible,
    especially under heavy incast and at high load. \kz{Not sure how we're framing
        incast.}
    %
    Like the reduction of smoothing, the effect of increased fan-in is for \texttt{Parsimon}\xspace to
    overestimate FCT distributions.
    %
    Similarly to above, we would also expect interposing an intermediate link
    between sources and the target link to reduce this error, so long as its
    bandwidth is selected appropriately.
    %
    We note however a trade-off between the complexity of the link-level simulation
    and the ease with which it can be optimized.
\fi

\Para{Lack of traffic smoothing.}
Similarly, any cross-traffic that shares a portion
of a path with traffic destined for the target link will tend to smooth out traffic
before it reaches the target.  \texttt{Parsimon}\xspace does not include any cross-traffic in its per-link
simulation, making it slightly overestimate the queueing delay at the target link.
Assuming the simulation is stable---that the arrival rate does not exceed the
service rate for any link---the target link will experience the correct
long-term average rate, but without as much smoothing as would happen in practice.
We see evidence of this effect in our evaluation, where error is slightly larger
for workloads with a predominance of short flows which would benefit more from smoothing.
Of course, correctly modeling the effect of cross-traffic on the traffic arriving
at a downstream link would be difficult to accomplish without reverting to a full network simulation.

\if 0
    When \texttt{Parsimon}\xspace generates a link-level workload, it
    preserves the arrival rate and burstiness profile of the input flows.
    %
    What's more, when the target link is not the first hop, sources fan in to it
    directly, since intermediate hops are removed.
    %

    %
    However, because our method removes any smoothing that could be caused by
    intermediate hops, the traffic at the target link could be burstier than what
    we would observe in reality, especially at high load.
    %
    This could cause \texttt{Parsimon}\xspace to overestimate the tail of FCT distributions.

    In our measurements, toggling overall burstiness from low to high has little
    effect on \texttt{Parsimon}\xspace's accuracy (\Sec{sensitivity}).
    %
    If desired, we could reduce this error---at the cost of some speed and
    increased complexity---by introducing an extra hop between sources and the
    target link.
    %
    The extra hop would approximate the expected magnitude of traffic smoothing,
    but we would need to ensure its contribution to link-level delays is not
    measured.
    %
    Doing so would require the additional assumption that link-level backends can
    report flow arrivals and departures on individual links, which is possible but
    makes them significantly less plug and play.
\fi

\Para{Link-level independence.} A more fundamental approximation is that
link-level simulations are treated independently.
This technique enables wholesale parallelization, but its accuracy depends on
the amount of correlation between the traffic intensities on the various hops
along the path. The more correlated the traffic, the more error \texttt{Parsimon}\xspace's method
produces.

First, consider the effect \texttt{Parsimon}\xspace's method will have on the FCT of a long flow.
If the intensity of the coresident traffic at each hop of the flow's path is
independent, then the flow's packets are unlikely to be backlogged on multiple
links at the same time---queueing, and the resulting end-to-end congestion
response, will happen at one link at a time.
Therefore, we would expect the flow to sometimes be backlogged on one link, and
at other times backlogged on another.
In this case, summing over the delay contributions of each link---as \texttt{Parsimon}\xspace
does when convolving the distributions---results in a good estimate
of end-to-end delay.
On the other hand, if the intensity of the coresident traffic were perfectly
positively correlated, the flow's packets could be backlogged on multiple links
during the \emph{same} time interval.
As before, the aggregation method would add the delays contributed by each
link; however in this case, doing so would produce an overestimate, because
during that time interval, only one bottleneck would contribute to end-to-end
delay.

For short flows, a primary effect of correlated traffic is to alter the
probability that a flow will encounter queueing.
Consider a single-packet flow that traverses two hops, both with load $l$.
If the traffic intensity over time along the two hops is independent, the
probability that the flow will encounter \emph{no queueing} is simply
$(1-l)^2$.
However, if both hops tend to have queueing at the same time, then the
probability of encountering no queueing is closer to $1-l$.

In very large networks with thousands of hosts and paths, and with realistic
workloads, we expect the effects of correlation to be small.
A basic result of queueing theory is that under some circumstances it is
possible to analyze queues independently, even when the output of one queue
connects to the input of another, so that queue behaviors are obviously
correlated. One view of our work is that we are empirically observing that data
center networks approximately admit product-form solutions for their
equilibrium state queue distributions under realistic workloads.

However, some networks
use PFC~\cite{dcqcn} to reduce packet loss due to go-back N error handling in some RDMA network
interface cards. Because PFC suffers
from head-of-line blocking, PFC can cause correlated congestion across multiple links, and so \texttt{Parsimon}\xspace would not
be a good choice for modeling such networks. If correlation is a problem, we could potentially measure
the degree of correlation and apply a correcting factor during the convolution step, but we leave that
for future work.

\if 0
    %
    That said, we still expect some degree of correlation.
    %
    In~\todo{ref eval}, we use microbenchmarks to assess its effect on accuracy,
    and we find it takes a large amount of correlated traffic to significantly
    degrade \texttt{Parsimon}\xspace's estimates.
    %
    It may be possible to assess the degree to which links on a
    particular path are correlated, and then to correct for any resulting
    overestimation in an ad-hoc fashion.
    %
    We leave these considerations to future work.
\fi
\Para{One bottleneck at a time.} Finally, in the convolution function,
we sum delays contributed by each link in the path rather than use a more
complicated function. The delay for a flow of a few packets is
well-modeled as the sum of the delay that those packets experience at each hop.
However, summing delays is less good for long flows that encounter simultaneous
cross-traffic congestion at multiple points along the path.  In this case, \texttt{Parsimon}\xspace
will ``double count'' those delays---the congestion control
protocol will (generally) back off based on the most congested link rather
than based on the sum of the simultaneous congestion.  \texttt{Parsimon}\xspace is more accurate
when the congestion is episodic and temporary, appearing at different links at different
times.

Congestion on any link (and therefore simultaneous congestion on multiple links) becomes
more common with higher network load, and we see this effect in our evaluation.
We can potentially correct for this bias by using a more complex function
for combining link delays when overall network utilization is high.
Because network operators are often willing to over-provision their network hardware
to reduce application tail latency, this is rare in practice.  For example, some recent
end-to-end congestion protocols, such as Homa~\cite{homa}, simply assume that network congestion
predominantly occurs at the last hop of each path.  We do not make such an assumption;
we handle congestion equally wherever it might occur.  However, we do assume that
congestion events are not persistent and network wide.

\vspace{4pt}

Each of these approximations is biased toward
producing overestimates rather than underestimates, because we expect network operators
to be more sensitive to over-promising tail behavior, even if that
comes at the cost of being too conservative with respect to capacity planning.
Additional analyses on the errors induced by these approximations can be found
in the appendix (\Sec{app-error-sources}).

\if 0
    With all of the error sources mentioned, we expect larger errors to manifest at
    higher loads.
    %
    It remains to determine how high load needs to be before we begin to observe
    more severe accuracy degradations; this and other related questions are the
    subject of \Sec{sensitivity}.
\fi

\section{Complementary Methods} \label{s:other-methods}
The previous section described how we decompose a single large network simulation into many small,
independent ones that can be executed in parallel and later combined. This section describes
additional optimizations that reduce, cluster, and prune these link-level simulations
for better computational efficiency. These reduce the number of cores needed
to simulate a given network within some time bound, or equivalently, the execution time
on a single server machine.


\if 0
    While these can be run in parallel given enough cores, another goal we also don't want them to
    do more work than necessary.

    \texttt{Parsimon}\xspace's link-level decomposition allows it to scale infinitely in the size of
    the simulated network, provided there are infinite cores and memory.
    %
    Specifically, \texttt{Parsimon}\xspace's simulation time is lower-bounded by the time it takes to
    simulate the longest-running link-level simulation, and link-level simulations
    need only be run long enough to collect enough samples for stable estimates.
    %
    However, this scaling property alone does not guarantee that simulations are
    particularly fast.
    %
    Recall from our description of the link-level topologies (\Sec{link-topos})
    that for each link in the network, \texttt{Parsimon}\xspace generates a topology with two to three
    hops from sources to destinations.
    %
    In addition to the extra memory requirement---which can be substantial for
    large networks---this has an adverse effect on simulation speed.
    %
    Since any packet that passes through any link in a full-fidelity simulation
    must also pass through a multi-hop link-level simulation in \texttt{Parsimon}\xspace, the
    decomposition method could necessitate simulating many more events in aggregate
    than a full-fidelity simulation would require.
    %
    The simulations would still be executed in parallel---with only a subset of the
    traffic per simulation---but the speed advantage is somewhat offset by the
    increased number of events, especially on a resource-constrained system.

    ns-3 provides
    more features than we strictly need.
    model much more than what \texttt{Parsimon}\xspace requires from a link-level backend.
    While \texttt{Parsimon}\xspace supports using ns-3 as a link-level backend, it also has the option
    of using a custom and minimal simulator that has been optimized for this
    purpose.%
\fi

\subsection{Fast Link-Level Simulation} \label{s:fast-sim}
By far the largest computational cost in \texttt{Parsimon}\xspace are the link-level simulations.
Initially we used ns-3 as our link-level backend.  However,
as a general-purpose simulator, ns-3 is designed to support arbitrary protocols with arbitrary
extensions, all the way down to hardware models. This is more flexible but
means that every packet in ns-3 generates events at every host, queue, and
link---as well as throughout the hosts' modeled network stacks.

Instead, we implemented a custom and minimal simulator optimized for high fidelity
single link simulation.
This backend only models the workload, topology, queueing, and
congestion control.
For congestion control, our prototype implements DCTCP's core
algorithm~\cite{dctcp} in a few tens of lines of code.  For example,
we do not need to model the mechanism for carrying ECN bits from switches
back to endpoints. Switching to a custom simulator speeds up the individual
link simulations by roughly an order of magnitude, with negligible loss of accuracy.
Reducing the simulation time of the worst case (most congested) link also reduces the
critical path dramatically. If more simulation features
are needed, \texttt{Parsimon}\xspace can use ns-3 at the cost of using more cores.

\subsection{Clustering and Pruning Simulations} \label{s:clustering}

\begin{algorithm}[t]
    \small
    \caption{Greedy link clustering \label{alg:greedy}}
    \begin{algorithmic}[1]
        \Let{unclustered}{\Call{AllLinks}{}} \Comment{links here are unidirectional}
        \Let{clusters}{[]} \Comment{list of list of links}
        \While{\textbf{not} {\Call{Empty}{unclustered}}}
        \Let{members}{[]} \Comment{new cluster}
        \Let{representative}{\Call{PopFirst}{unclustered}}
        \State \Call{Push}{members, representative} \Comment{with initial member}
        \For{candidate \textbf{in} unclustered} \Comment{find other members}
        \Let{rfeature}{\Call{Feature}{representative}}
        \Let{cfeature}{\Call{Feature}{candidate}}
        \If{\Call{IsCloseEnough}{rfeature, cfeature}}
        \State \Call{Push}{members, candidate} \Comment{new member}
        \State \Call{Remove}{unclustered, candidate}
        \EndIf
        \EndFor
        \State \Call{Push}{clusters, members}
        \EndWhile
        \State \textbf{return} clusters
    \end{algorithmic}
\end{algorithm}

Lastly, we recall that \texttt{Parsimon}\xspace's decomposition results in two simulations per
link: one in each direction (\Sec{link-workloads}).
On a large-scale 6,144-host topology we use for evaluation, there are over
9,000 links, and therefore over 18,000 simulations generated.
Fortunately, data center topologies commonly induce symmetries that render some
of these simulations redundant.
For example, up-links in the same ECMP grouping can be assumed to have the same
characteristics and traffic patterns.
Furthermore, the workloads themselves may also induce symmetries due to
communication patterns and load balancing~\cite{fb-network}.

We can take advantage of these symmetries by clustering links that carry similar
traffic and only simulating one representative from each cluster.
Then, in each cluster, all links inherit the delay distribution produced by the representative link.
\texttt{Parsimon}\xspace's clustering requirement is quite specific, which limits the range of
popular clustering algorithms that can be used.
Let $l_1, l_2 \in L$ be any two link-level simulations, and let $d : L \times L
    \rightarrow \mathbb{R}$ be a distance function.
Ideally,
\vspace{-1mm}
\begin{equation*}
    l_1 \text{ and } l_2 \text{ are clustered together} \iff d(l_1, l_2) < \epsilon,
    \vspace{-1mm}
\end{equation*}
where $\epsilon$ is some bound.
The left-to-right direction preserves accuracy; the
right-to-left supports efficiency.
Most centroid-based and density-based clustering algorithms aren't designed to
provide the left-to-right property. Instead, \texttt{Parsimon}\xspace uses \Alg{greedy}.
This algorithm greedily clusters simulations together, using a distance function that
predicts which links will have similar delay profiles. In our prototype, we
check that the link flow size and inter-arrival time distributions---as well as
their load levels---are close. We find this provides a reasonable tradeoff
between efficiency and accuracy, but users can turn off the optimization at the cost
of using more cores. Further details about the clustering can be found in the appendix (\Sec{more-clustering}).


\section{\texttt{Parsimon}\xspace Overview} \label{s:overview}

\begin{figure*}[t]
      \centering
     
      \includegraphics[width=\linewidth]{figs/overview.pdf}
      \vspace{-8mm}
      \caption{\small
            Overview of \texttt{Parsimon}\xspace.
           
           
           
            First, for any path, \texttt{Parsimon}\xspace estimates the contribution of each
            component link to delays in flow completion times, represented as a
            probability distribution.
            %
            \texttt{Parsimon}\xspace then combines delays along the path using Monte Carlo
            simulation (see \Sec{key-methods}).
            %
            Further, for added performance, link-level simulations are
            optimized and redundant simulations (due to {e.g.,}  ECMP or symmetries
            in workload patterns) are pruned (see \Sec{other-methods}).
      }
      \label{fig:overview}
      \vspace{-1mm}
\end{figure*}

\begin{figure}[t]
      \centering
      \includegraphics[width=0.95\linewidth]{figs/workflow.pdf}
      \vspace{-4mm}
      \caption{\small
            An illustration of \texttt{Parsimon}\xspace's workflow.
            %
            All inputs and outputs are shown in the top row.
            %
            Rectangular boxes are inputs and outputs, rounded boxes are
            intermediate artifacts, and ovals are \texttt{Parsimon}\xspace's actions.
      }
      \vspace{-4mm}
      \label{fig:workflow}
\end{figure}

This paper describes a set of methods to quickly and scalably estimate flow performance
in data center networks.
These techniques are implemented in a prototype called \texttt{Parsimon}\xspace, designed to
provide the following:
\begin{CompactItemize}
      \item {\bf Fast, scalable estimates.} We aim to supply
      estimates two to three orders of magnitude faster than full-fidelity simulation.
      Given enough cores, execution time should remain bounded regardless of network size.
     
      \item {\bf Tight latency bounds, including tail performance.}
      Our approximations bias slightly towards overestimation, but still provide
      close estimates even for the 95th or 99th percentile of the distribution
      for a given flow length.
      \item {\bf Minimal restrictions on topology and workload.} Our methods
      are largely independent of both topology and workload, although some combinations
      of topology and workload will have lower accuracy.
\end{CompactItemize}

\Fig{overview} illustrates the intuition behind its core method, and
\Fig{workflow} depicts its workflow.
The user supplies 1) a description of the topology, as a set of
nodes and links, and 2) the workload, as a set of flows and routes.
In our implementation, we generate the flow list by sampling from the traffic matrix and
the flow size distribution, with inter-arrival times determined by a burstiness
parameter.
Once inputs are supplied, \texttt{Parsimon}\xspace proceeds in several steps:

\Para{Decomposition.} To start, flows are assigned to each link they traverse,
e.g., for a fat tree using ECMP.
Then, for each link $l$, \texttt{Parsimon}\xspace generates a custom backend simulation with a topology
selected to determine---as accurately as possible---the \emph{contribution of}
$l$ to the end-to-end flow completion times (FCTs) of the flows passing through it.
Each of these backend simulations can run in parallel.

\Para{Clustering.}
Depending on the size of the topology,
there may be tens or hundreds of thousands (or more) of link-level simulations
to perform.
Fortunately, data center topologies exhibit notable symmetries, and industry
has reported that the same is true for many of their
workloads~\cite{fb-network}.
\texttt{Parsimon}\xspace can optionally cluster links with similar workloads together.
Only one representative from each cluster need be simulated; the rest of the
link-level simulations are pruned.
Clustering is discussed in more detail in \Sec{clustering}.

\Para{Simulation.} The next step is to simulate all cluster representatives in
parallel.
The decomposition step resulted in a topology and a workload for each
link-level simulation, and we can use any simulation backend.
Our prototype supports two: ns-3 and a custom
high-performance link-level simulator (\Sec{fast-sim}). This allows us
to directly validate our link-level simulator against ns-3. However, other
efficient models, such as fluid flow~\cite{fluid} or machine learned
models could be used here instead, for different tradeoffs of performance
and accuracy.
Each link-level simulation produces a distribution of the delay contributed
by that link to the flow completion time (FCT), bucketed by flow size.
Note this is not the link's
propagation delay---we calculate that contribution directly from the topology.
These distributions---described in the next section (\Sec{key-methods})---are
organized according to the original input
topology, as depicted in \Fig{overview}.
Recall that only one representative from each cluster is simulated; every other
link is populated with the distributions of its cluster representative.

\Para{Aggregation.} The last step is to aggregate the link-level results into
estimates for entire paths through the network.
These estimates are also represented as delay distributions.
Conceptually, \texttt{Parsimon}\xspace obtains a delay distribution for a path by convolving
together the appropriate distributions from each of the path's component links.
Since there are multiple distributions per link and potentially many paths
through the network, we do not compute convolutions up-front.
Instead, convolution is done on-demand via Monte Carlo sampling; a by-product
is that we can efficiently produce estimates for individual source-destination pairs,
virtual networks, or classes of service.
To make a single point prediction for a flow taking some path through the network, \texttt{Parsimon}\xspace
uses the flow size to find the appropriate distribution for each link, samples a value from each of them, and
combines them together.  This process is repeated for each flow.

\vspace{4pt}
At a bird's-eye view, \texttt{Parsimon}\xspace's method is simple: to accelerate FCT estimates, we
estimate the effect of each link independently and in
parallel.
Then to make predictions about the whole network, we combine the results.
However in our experience, the accuracy of the method hinges tightly on the
quality of the link-level estimates and subsequent aggregation.
For example, when generating the backend simulations, we have observed that
failure to adequately capture pertinent features of the network severely
degrades the quality of \texttt{Parsimon}\xspace's estimates.
Similarly, link-level results must be processed and aggregated with care to
preserve accuracy across all flow sizes.
The next section describes these techniques in detail.


\section{Related Work}