Introduction

Recently, Coffman and Odlyzko released an AT&T Labs Research Report stating that Internet data traffic is doubling each year [26]. During 1997, the Internet was shipping between 2,500 and 4,000 TB/month. By year-end 1999, they estimate that the amount of Internet traffic is between 10,000 and 16,000 TB/month, an increase by a factor of four over a two year period.

However, the estimated traffic patterns are largely based on historical data. The next ``killer app'' could drive demand well beyond capacity and such ``killer apps'' are hard to predict. The latest ``killer app'' is peering software like Napster [73] and Gnutella [50], which provides the the ability to share MP3 files over the Internet. Since its release in 1999, Napster has garnered 25% of the total traffic on many university networks. Some schools are reporting percentages as high as 50%.

Even more problematic are popular applications produced by a single site. SETI@home [89] makes use of idle CPU time on network connected personal computers to search for signs of extraterrestrial life in signals collected by large radio telescopes. During its first year, the traffic generated by SETI@home accounts for a third of the outgoing traffic at U.C. Berkeley.

Similarly, explosive data growth rates are likely to occur due to the pervasiveness of web-enabled phones and wireless PDAs, such as the Palm VII. While these devices are bandwidth limited to $\approxeq$10KB/sec, the sheer number of these devices could single-handedly increase the Internet traffic demand over the previous predictions by 30%.

Unfortunately, bandwidth is does not appear to be growing as fast as expected. Bill Gates predicted in 1994 that we will have ``unlimited bandwidth'' in the next decade. George Gilder predicted that bandwidth would triple each year for the next 25 years [49]. Both of these predictions are far of the mark. According to Coffman and Odlyzko, high-bandwidth systems, such as WDM, will only grow from today's rates of 800 GB/second to 6.4 TB/sec in 2007, or double each year for the next 6 years.

Consequently, short falls in available bandwidth may result. Because of the shrinking capacity relative to demand, real-time network management will be absolutely necessary. In particular, network managers will have to contend with new ``mobile killer apps'', Sun's Jini technology [104], that have the capacity to generate dynamic surges in traffic across the Internet.

The predominate technique used to analyze network behavior is discrete-event simulation. However, the computational requirements of this problem are immense. Network designers will require tools that can efficiently model a network with potentially millions of nodes and data streams on the order of millions to tens of millions. These tools will enable better network configurations and more efficient, accurate management of capacity.

To address this problem, we propose a new optimistic parallel simulation modeling technique called reverse computation. Here, network models are able to execute both forward and backward in simulated time. We divide reverse computation models into two classes: time-proportionate and perfect. Time-proportionate reverse computation (TiPRC) [40] stores only the minimum set of control information generated by the forward processing of an event. One can view this control information as the ``entropy'' produced by the processing of this event. This is called time-proportionate because reverse execution is limited by how much garbage is produced. Once memory is exhausted, the garbage must be reclaimed before forward execution can resume. This technique is used to support the ``undo'' operation in optimistic parallel simulation. TiPRC has been shown to reduce the state memory requirements of optimistic simulations by a factor of 100 and increased the overall speedup by a factor of 6 when compared to classic state-saving or logging techniques.

Perfect reverse computation (PRC) is a radical extension of TiPRC that produces no effective ``entropy'' in the forward or reverse processing of an event, thus allowing the simulation to run arbitrarily long in a constant amount of space. Our hypothesis is that under PRC, events in the optimistic simulation can be immediately committed. Instead of ``rolling events back,'' simulation objects shift from forward processing to reverse processing. The immediate advantage of this modeling methodology is that global virtual time (GVT) calculations and fossil collection (i.e., garbage collection) are no longer needed. Thus, PRC holds the promise of allowing large-scale network models to scale to much larger processor configurations than TiPRC or previous parallel simulation systems.

However, the real power of PRC is not so much the speed of an individual simulation run but its ability to execute models forwards and backwards. This capability allows the modeler to ask questions about the model that can be answered in a few simple runs and not necessarily require an exhaustive $2^K$ factor simulation study. It this modeling power that we believe makes PRC worth the potential complexities and could result in a pervasive and paradigm-shifting impact on the parallel/ distributed computing and general simulation communities.

The overall goal of this project is to understand the fundamental functional and performance limits of reverse computation when applied to the modeling of large-scale systems. Because of its importance and impact, we have selected network models as our driving application. To achieve this goal, we propose to investigate reverse computation in the following five major research thrust areas:

1. the design and implementation of perfectly reversible computation (PRC) algorithms for event-list management, and time management to enable scalable, efficient optimistic event processing,

2. the development of processes and techniques to effectively model a large-scale, multi-protocol network scenario in a parallel simulation, reverse computation framework,

3. the comparison and contrast of PRC performance to TiPRC and state-of-the-art conservative synchronization techniques,

4. the exploration of the linkages between PRC, quantum computing and classic parallel/distributed computing that could lead to a more unified view of these disparate classes of computation, and

5. the creation of new methods and techniques for the design of simulation experiments that take advantage of reverse computation (PRC).