This document serves as an easy-to-follow introduction to Dartmouth SSF, that covers its usage, history, as well as some theory background. It should not be treated as a thorough material and does not cover every aspect of DaSSF. For illustrating the use of DaSSF, we only describe those basic modeling capabilities provided by SSF API in general and some of the functionality specific to SSF C++ bindings. A brief history of Dartmouth SSF and a little discussion on DaSSF kernel are also included to familiarize users with a bit deeper understanding. For better description of the use of DaSSF, refer to DaSSF User's Manual (given in the side bar). General descriptions on Scalable Simulation Framework API can be found in SSF API Specification (also given in the side bar).
Table of contents:
- DaSSF 3.1 User's Manual [603K
postscript]
- SSF API Specification 1.0 [54K
pdf]
- Click here to SSF Research Network
| Introduction |
Simulating global networks were hindered by many problems. The internet is what described by Paxson and Floyd as "an immense moving target". Its pure size, heterogeneity, and rapid change pose a challenge for simulating its behavior. The key strategies for developing simulations in the face of these difficulties would be:
- Using parallel simulators that expands space and time limitations of traditional sequential simulators;
- Providing a lean and self-configurable simulation API;
- Making the simulator scalable.
Scalable Simulation Framework (SSF) is developed as a common parallel simulation API suitable for but not exclusively for simulation of very large telecommunication systems. It promises consistent and compact interface, which is platform independent. "It is the next-generation core-modeling interface".
Dartmouth SSF (DaSSF) is a C++ implementation of SSF. There are several achievements by DaSSF which out-performs its rivals:
- Capacity: DaSSF is able to simulate very large network models efficiently. Usually these network models contain thousands up to millions of entities (e.g. hosts, routers, etc.)
- Simplicity: DaSSF API simplifies the expression of models by providing both process-oriented and event-oriented world views. It is possible for user to express model with high-level of abstraction, while still achieving decent performance.
- Scalability: It's important for DaSSF to scale as the simulation model grows larger. DaSSF's implementation of time line makes a significant contribution in keeping the performance from degrading as more entities and events are added to the system.
Like many other existing simulators, DaSSF provides a set of C++ class libraries and a runtime system; one builds a model by writing C++ program which consists of classes derived from the given classes. By the rule of simplicity, the class library consists of only five principal classes: Entity, Process, Event, inChannel, and outChannel. An Entity is a container for state variables. In a simulation model, an Entity can be a physical object (e.g. a router in the simulated network), or a virtual object (e.g. a protocol). inChannels and outChannels belong to entities; they are used to connect entities by mapping inChannels with the corresponding outChannels. Events are passed through the mapped channels like messages in a computer network. Code associated with an entity may send an Event by writing it to an outChannel. Likewise, code associated with an entity is triggered to execute upon receiving an event on an inChannel. Process, as its name stands for, serves exactly the same as a process in the process-oriented simulation world view. It's a special C++ function which is executed along with the progress of simulation time. The function consists of code fragments separated by wait functions, which potentially blocks the process until the condition it waits on is being satisfied. A process can wait for a period of simulation time, or wait on any event to show up in a channel. The code fragment between these wait functions can be arbitrary computation, which takes zero simulation time. It serves to update the state variables in entities.
These five base classes provide a truly generic and maximally compact
interface that is sufficient to model not only telecommunication
networks, but also many other domains. It uses process-oriented
simulation approach which simplifies the modeling effort.
| A brief history |
Dartmouth SSF took place as a need for simulating very large scale communication networks. The first language that answered the call is Telecommunications Description Language (TeD), developed at Georgia Tech by Richard Fujimoto and Kalyan Perumalla. It is part of Simulation of Integrated Communications Systems (SICS) project, a joint project including researchers at Bellcore, Bell Labs, Dartmouth College, Georgia Tech, University of Massachusetts, and Rutgers University. TeD/GTW is the first implementation of TeD language which provides a translator that converts TeD descriptions to parallel simulation software that executes on the Georgia Tech Time Warp (GTW) system. Participating groups used TeD to develop large-scale network models with complex protocols, e.g TCP/IP, ATM PNNI, multicast and wireless protocols.
Such effort continued into Scalable Self-organizing Simulations (S3) project. Dartmouth developed TeD/Nops, which is based on a conservative parallel simulation engine. Nops was developed by David M. Nicol and Anna L. Poplawski. The success of Nops encouraged us to continue pursuing a full-fledged highly efficient conservatively synchronized simulator, suitable for very large scale simulations of multi-protocol communication networks.
The goal of project S3 is to achieve radical improvements in speed, scalability, and manage-ability of modeling and simulations of communication networks. Towards this end, Scalable Simulation Framework programming interface (SSF API) was invented by James Cowie, David Nicol and Andy Ogielski. It is the next generation core-modeling interface. SSF API promotes high efficiency without a need for separate framework language like TeD. Dartmouth SSF was developed by Jason Liu and David Nicol. Convincing simulation results are reported by complex big internet models simulating hundreds of thousands of network components running realistic network protocols (e.g. BGP, OSPF, TCP/IP).
DaSSF was first made public in the fall of 1998. Major changes and
upgrades followed as SSF specification was developed. Until the spring
of 2000, DaSSF implementation was stabilized in version 1.0.6. DaSSF
1.0 is based on a window-based synchronous parallel simulation
kernel. The synchronization protocol has been proven to be scalable for
large-scale discrete-event simulations. In the summer of 2000, DaSSF 2.0
was implemented with an asynchronous protocol. Results have shown that
for certain applications, DaSSF 2.0 performs much better. However, there
are also other applications with which DaSSF 1.0 can achieve better
results. This motivated us to design and implemented a mixed
synchronization kernel, which was incorporated in DaSSF 3.0. The mixed
synchronization showed much better performance than the synchronous or
the asynchronous protocol that stands alone. Also, DaSSF 3.0 supports
distributed memory platforms. It takes the approach of having separate
synchronization schemes for shared memory and distributed memory. A wide
variety of machine platforms are supported by DaSSF 3.0.
| Examples |
It's better to illustrate the use of Dartmouth SSF classes using examples. The examples used here are only served to highlight how we use DaSSF and bear no pretension to realism. The examples discussed in this session can be found in the app directory of DaSSF distribution.
A description of the following example is taken from the DaSSF 3.0 User's Manual. The example is rather comprehensive and contains a large portion of DaSSF features. You are not supposed to understand every aspect of the example. Refer to the manual for better understanding of specific details.
The following two examples show the use of DaSSF 1.0. The API changed since DaSSF 3.0 to cope with distributed memory environment. They are nonetheless listed here in case people want to resort back to the old version for compatibility.
- helloworld is a very simple example where the system is consist of only one entity having two processes, a sender and a receiver. The sender process periodically writes events on the out-channel, which maps to its in-channel; the receiver process waits on the in-channel and counts the number of arrival events.
- muxtree builds a simplistic network of switches. The network topology is of an in-tree, the leaves of which are traffic generators. Packets generated from the source travel through the switches and flow to the tree root, experiencing delays and possible losses along the way.
| Design and implementation issues |
DaSSF 3.0 Kernel
DaSSF 3.0 supports distributed memory. It takes the approach of
having separate synchronization schemes for shared memory and
distributed memory. At global level, the model is partitioned into a
number of subsystems, each of which resides on a processing node and
synchronizes with other subsystems via message passing. At local level,
on each node, the subsystem can be further partitioned onto multiple
processors of the node. The synchronization between these processors on
a single node is through shared memory. The following figure depicts
the organization of our system. The figure shows an example where the
system consists of four processing nodes connected by an
intercommunication network. On each node, there are two processors
synchronizing via shared memory with each other conducting simulation
for the submodel that is statically assigned to it from the initial
partitioning.
Model partitioning is done automatically. DaSSF 3.0 also includes a new mixed synchronization kernel that combines synchronous and asynchronous conservative synchronization protocols. The composition achieves better performance as it allows the kernel to tailor the synchronization mechanism ot the model being simulated. The kernel can automatically find the optimal combination of synchronous and asynchronous channels between logical processes.
DaSSF 2.0 Kernel
DaSSF 2.0 is implemented with asynchronous parallel synchronization protocol. The asynchronous kernel schedules logical processes based on critical channel scanning. For certain applications, asynchronous protocol is attractive as it avoids pitfalls associated with the synchronous protocol. For example, synchronous protocol is much more sensitive to small latency, which has greater impact on the global barrier synchronization. It is important to note though that the overhead for asynchronous protocol can be significant for LP graphs with high node degree.
DaSSF 1.0 Kernel
DaSSF 1.0 is a synchronous, conservatively synchronized parallel simulator. It uses a window based synchronization protocol that is proven to be scalable. Unlike optimistic approach that adopts rollback and recovery technique, implementation for synchronizing logical processes is simple, elegant, and best of all, scalable. DaSSF exploits lookahead by computing the distances between clusters of entities (called timelines). An event delivered to the channel at one timeline will reach the other side of the channel at another timeline with delay no less than the smallest channel delay of the whole system. With this guarantee, we advance the simulation based on windows, the size of which being the smallest channel delay. For very large simulation models, there will be enough work per window to amortize the cost of synchronization.
DaSSF exploits the notion of timeline which clusters entities (i.e. logical processes). Entities that belong to the same timeline can access each other's state variables. Therefore, it improves communication cost among entities and at the same time reduces modeling complexity. Utilizing a well-behaved data structure called binque, an extension to calendar queue, it guarantees scalability for distributing and processing events among multiple processors.
DaSSF uses its own thread system through source-code level transformation to conserve memory usage. Self-threading gives complete control over scheduling mechanism and helps minimize overhead. The transformation is made on C++ source code with the help of user annotations in the source code. The transformation takes care of C++ language features, e.g. virtual functions.
DaSSF automatically partitions the simulation model and is capable of balancing workload at runtime. During simulation, a starving processor may "steal" available workload from other processors. A timeline is the smallest workload that can migrate among processors.
