New Modeling Techniques

For a computation to be perfectly reversible it must be deterministic and not split in either the forward or reverse event processing case. During the processing of a single event, LPs may schedule multiple events to other LPs. In the context of network models, packet generator LPs will schedule the arrival of a new ``packet'' to router LPs as well as schedule a ``wake-up'' event in the future to itself that determines when the next packet will be generated. We propose to devise an efficient and correct methodology for reversing these ``splits'' by utilizing LP type and network topology information.

In network simulation models, there are typically generator LPs, which never receive external events, echo LPs, which receive external events and forward them to other LPs, and sink LPs which only receive external events but do not schedule external events. As previously discussed, generator and sink LPs are duals of one another. A generator LP will switch to being a sink LP and a sink LP becomes a generator LP during reverse execution. Thus, we believe these ``splits'' will not have to be tracked down to reverse execute either of these LP types. We also observe that echo LPs will typically only schedule a single event into the future, thus the split problem can be avoided with that LP type. In cases where the echo LPs generate ``splits'' by scheduling multiple events in the processing of a single event, we plan to utilize the static network topology information to facilitate the reversal of these splits.

Another issues concerns the creation of symmetric entry/exit conditions in branches and loop statements. Recall from the previous discussion that separate code paths are used to support forward and reverse execution. However, we need to insure that the exit condition of a branch or loop is the entry condition in the reverse code path and vis-versa.

Overall, there is a fundamental limitation on what kinds of models can be simulated using reverse computation. We propose to find those limitations and devise modeling techniques that make PRC as efficient and practical as possible.

We do note that these constraints are not as restrictive as it first sounds, when placed in the context of discrete-event simulation. Determinism and repeatability are usually required features of any analytic, discrete-event simulation. Moreover, queueing networks represent the dominate class of models simulated using the discrete-event technique. This class performs mostly ``counting'' operations in the form of increment and decrement, such as counting packet losses. Thus, avoiding the use of destructive assignment in the creation of large-scale models is plausible.