2026. 3. 25. 21:03ㆍComputerScience/Computer Architecture
Interconnection Networks, Simulation
simulation is a double-edged sword — while it can provide excellent models of complex network designs, simulators and simulations are equally complex. To that end, the quality of simulation results is only as good as the methodology used to generate and measure these results. In this chapter, we address the basics of simulation input, measurement, and design. Not all network simulators need to model the intricate details of router microarchitecture, and we begin with a discussion of the different levels of simulation detail available to a network designer. As important as choosing the appropriate modeling accuracy is selecting the workload or input for a network simulation.
Levels of Detail
Before simulation of a network begins, the designer must choose an appropriate level of detail for the simulation. Using an extremely accurate simulator is always safe in the sense that modeling inaccuracies will be avoided, but it is also expensive in terms of the time required to both write and run the simulator. A more reasonable and efficient approach is to choose a level of simulation detail that will capture the aspects of the network’s behavior important to the designer and avoid simulating unnecessary details of the network.
Network Workloads
The most realistic traffic patterns are application-driven workloads generated directly by the clients using the network. For example, in a shared-memory interconnect, the network traffic consists of coherence messages send between the various processing nodes. If we model not only the network, but also the application running on the processors, our workload is exactly that required by the application. While application-driven workloads give us the most accurate modeling of the network, it is often difficult achieve a thorough coverage of expected traffic with these methods exclusively. Following our shared-memory example, workloads are tied directly to applications, so expanding the set of workloads involves creating new applications, which is generally quite expensive. Alternatively, a carefully designed synthetic workload can capture the demands expected for the interconnection network, while also remaining flexible.
Application-Driven Workloads
This “full-system” simulation approach is often called an execution-driven workload. An execution-driven workload is certainly accurate, but one drawback is that feedback from the network influences the workload. This can make it difficult for a designer to isolate bottlenecks in the interconnection network — any change in the network design not only affects the network, but it can also affect the workload.
An alternative to simultaneously modeling the network and its clients is to instead capture a sequence of messages from an application of the network and then “replay” this sequence for the network simulation. These trace-driven workloads can either be captured from a working system or from an execution-driven simulation.
In a trace captured from an execution-driven simulation, the network being simulated might offer only a low level of detail so the simulation can be performed quickly. This trace could then be reused for a detailed simulation of the network only. Since the traces are captured in advance, feedback from the network does not affect the workload. Although this can reduce accuracy, for some applications this may not be a significant issue.
Synthetic Workloads
As mentioned previously, application-driven workloads can be too cumbersome to develop and control. This motivates the inclusion of synthetic workloads, which capture the salient aspects of the application-driven workloads, but can also be more easily designed and manipulated. We divide our discussion of synthetic workloads into three independent axes: injection processes, traffic patterns, and packet lengths.
In some situations, these axes may not be truly independent and we highlight this issue in Exercise 24.3. The first parameter of interest for any injection process is the average number of packets it injects per cycle, or its injection rate. Perhaps the simplest means of injecting packets at a rate r is with a periodic process.
Simulation Measurements
When estimating network performance, there are two main sources of error: systematic error and sampling error [66]. Systematic errors are errors introduced by bias in the measurements or simulation itself and for network simulation are generally a result of the initialization of the simulator. By choosing an appropriate warm-up period for a simulation, as discussed in Section 24.3.1, the impact of systematic errors can be minimized.
Once the network is warmed up, it has necessarily reached a steady state. That is, the statistics of the network are stationary and no longer change with time. At this point, the focus shifts to sampling the network so that an accurate estimate of a particular network parameter can be determined. Two common sampling approaches, the batch means and replication methods, are presented in Section 24.3.2.
Simulator Warm-Up
as buffers begin to fill up, later packets see more contention, increasing their latencies. Over time the influence of the initialization becomes minimal, and at this point the simulation is said to be warmed up. By ignoring all the events that happen before the warm-up point, the impact of systematic error on measurements can be minimized.
1. Set the initial warm-up period Twu based on a heuristic.
2. Collect statistics, ignoring samples during the estimated warm-up period.
3. Test the remaining samples to determine if they are stationary. If stationary, use Twu as the warm-up period. Otherwise, increase Twu and repeat steps 2 and 3.
By averaging several independent simulator runs into an ensemble average, this sampling error can be greatly reduced. Figure 24.5 shows that with an ensemble of 10 independent simulation runs, the system appears to stabilize after around 4,000 sample points.
Steady-State Sampling
Given a simulation that has reached steady state after an appropriate warm-up period, the next step is to measure the underlying process. We present two basic approaches for making these measurements, the batch means method and the replication method, both of which are reasonable techniques to use in a network simulator.
In the batch means method, measurements are taken from a long, single simulation run. Like the batching used to smooth the samples when determining the warm-up period, the samples are split into many batches and statistics are first accumulated for these batches.
The main drawback of the batch means approach comes from an analysis of its statistical implications. Ideally, one would want each batch collected to be independent from all the other batches. Otherwise, measures such as the overall mean¯B could be biased by correlation between the batches. In reality, batches from a single simulation run are not independent because the packets queued in the network at the end of one batch remain in the network at the beginning of the next batch. This effect can be reduced by making the batches as large as possible, which explains the choice of using only 20 to 30 total batches.
An alternative sampling approach, the replication method, solves the problem of correlation between batches by taking samples from many independent runs of the network simulator. Instead of a single long run, as in batch means, several smaller runs are collected.
While replication eliminates correlation between the mean samples Ri , it is more susceptible to systematic errors introduced by initialization. Unlike the batch means method that has only a single initialization to affect the samples, many initializations are performed in the replication method. To minimize the impact of this on the replication means, it is suggested that 5 to 10 times more samples be collected in each run as were discarded during the warm-up period.
Simulation Approaches
There are two common approaches for designing a network simulator: cycle-based and event-driven simulation. To explain both design approaches and highlight their differences, we will use both to model a simple output-queued router node. In this node, arriving packets are immediately forwarded to a single output queue corresponding to their output port. The output queues have enough write bandwidth to simultaneously accept packets from all the input ports. For simplicity, the total delay of the node is assumed to be one simulator cycle, and an infinite buffer will also be used.
In cycle-based simulation, time proceeds in two phases, generally, one phase is loosely associated with reading global state and the other with writing that state.
the critical invariant is that all the functions within a phase can be evaluated in any order without changing the outcome of the simulation.
An alternative to cycle-based simulation is event-driven simulation. Unlike cycle- based simulations, event-driven simulations are not tied to a global clock, allowing for significantly more flexibility in modeling. This is especially useful when the underlying design is asynchronous. Event-driven simulations are built on a very simple framework of individual events. Each event is a data structure with three fields: an invocation time, an action (function call), and data (function arguments). Simulation proceeds by creating a event queue of all pending events
Simulation begins with the creation of an Arrival event for a packet at a given node. As before, the arriving packet is queued corresponding to its output port, but in the event-driven simulator, we also need an event to trigger the scheduling of output.
Again, any events assigned to the same time step must be able to be performed in any order without affecting the correctness of the simulation.
Unlike the simple two-phase simulation loop of a cycle-based simulator, an event-driven simulation must maintain a sorted list of events in order to determine the next event to be executed. Additionally, insertion into this list should be efficient. This naturally leads to a heap-based implementation.
Troubleshooting
As with most simulators, the best methodology for using them is to first develop an intuition and back-of-the-envelop or modeling calculation for the results that you expect. Then use the simulator to verify this intuition. If you follow this procedure, most of the time your results will be close to that of the simulation. However, there will be disagreements from time to time and there are some general techniques for tracking down these problems in a network simulator:
1. Verify that you are simulating your network with enough detail.
2. Check for unfairness or load imbalance between resources. This is an especially common problem and is often overlooked by simple models.
3. Narrow down the problem by identifying the bottleneck resource. For example, if you increase the flow control resources (such as the number of virtual channels and buffer sizes), but a network still under-performs a throughput estimate, then the flow control is probably not the culprit. Now continue with the routing function, and so on.
4. Gather statistics. Is all the traffic going where it is supposed to? Are a few packets staying in the network much, much longer than the majority? Anomalies in statistics are often a good clue.
5. Configure the simulator to a simple case, such as uniform traffic, Bernoulli arrivals, low offered load, and large buffers, so it can be compared to an analytical solution.
6. Simulators can have bugs, too. Compare against another simulator or delve into your current simulator’s code.