SB-RTPA: SIMULATION-BASED REAL-TIME PERFORMANCE ANALYSIS USING AGGREGATION OF SHORT SIMULATIONS

This dissertation introduces a new evaluation paradigm for worst-case traversal times based on aggregation of simulations. As the complexity of real-time networking systems and applications grows, classical methods face increasing challenges. Oftentimes, analytical methods that provide guarantees on the maximal end-to-end latencies are not available, too pessimistic, or too expensive to develop.
The traditional approach to evaluating such systems via simulation requires running long simulations that apply synchronized node start offsets and randomized clock drifts to explore the simulation state space. Running long simulations, however, has significant implications on the design process as they take a long time to be executed, limiting the variations and number of candidate solutions that the designers of such systems can consider. It is observed in this dissertation that long simulations can be rather inefficient as a significant portion of the computational effort is typically spent in states of low interference between flows, which has a reduced probability of causing high end-to-end latencies.

The paradigm proposed by this dissertation aims to mitigate these shortcomings by running many short simulations and aggregating their results. In all test cases applied in this work, end-to-end latencies equivalent to long simulations were observed but for a fraction of the resources. The speedups observed with these simple techniques reached up to a factor of 266, without even considering additional speedups that could be gained via the increased parallelization potential of the approach.

First, the general potential of simply splitting up the long simulations into shorter ones is evaluated, and both synchronized and uniformly sampled node start offsets for running and aggregating these short simulations are investigated. Increases in median latency on a per-flow basis of up to 25.8% are observed for the considered test cases.

To improve the effectiveness and efficiency of the approach, a heuristic to determine an optimized simulation time that maintains the speedup factor is proposed, together with an improved method to sample the node start offsets, namely stratified sampling.
The heuristic to select the simulation time is based on a pretest executed on a small fraction of the total simulation budget. First, half of the budget dedicated to this pretest is used to determine a reference speedup factor. Then, in increasingly smaller slices of the other half of the budget, speedups for increasingly shorter simulation times are determined until they drop below a certain threshold with respect to the reference speedup. This yields the choice of the simulation time.

The improved sampling of node start offsets is based on overlapping stratification over exponentially growing sampling ranges. This approach allows the exploration of diverse solutions while also integrating the high initial interferences observed by the solutions close to the synchronized case, as exploited by the traditional approach. This technique allows a good trade-off between exploration and exploitation of the search space of starting conditions.

Finally, the maximization of the observed end-to-end delays is modeled as a multiobjective optimization Pareto problem. NSGA-II, a popular algorithm to address such problems, is applied. A biased population is initialized based on stratified sampling. The optimization efficiency and effectiveness are then evaluated on two different optimization variations. One variation optimizes only the node start offsets and applies changing random seeds to each simulation to explore the flow orders. The other variation additionally optimizes the flow scheduling order by introducing and adjusting very small frame offsets to control the sending order of flows scheduled simultaneously without impacting the traffic properties.

The evaluation paradigm developed in this dissertation proves to be beneficial for both generating tighter approximations of worst-case traversal times via simulation and reaching results equivalent to long simulations in a small fraction of the simulation time. Additionally, the approach enables the use of highly parallel infrastructure, such as HPCs, as short simulations are independent of each other and can thus be run in parallel.
This opens up paths to exciting future research and applications, including improved optimization and advanced learning methods. It further allows for more responsive and effective design paradigms by exploiting the increased efficiency and parallelization potential, significantly reducing the friction in the typically iterative design process.