[Ns-developers] About ns-3 multi-threaded simulator implementation

[Guillaume Seguin]

Greetings ns-3 developers,

For the past few weeks I've been working on a multi threaded implementation
of the ns-3 simulator, and I've got a pretty-much-working version since this
morning.

Algorithm basics
================
This implementation is based on the Chandy, Misra, Bryant null message algorithm
for simulation synchronization. Basically, the network is split in partitions
(with one partition per node for now) which have their own event queues and
clocks. The event queue of each partition can then be processed until the
partition clock has advanced to a date which is defined as the maximum date
before neighboring nodes may send us new events, so that processing events
before this date is safe from a simulation consistency point of view.
This maximum date is computed using neighborind nodes clocks and a minimum
transmission delay, called the /lookahead/, which is based on the transmission
channel.
When a partition clock has reached this maximum date, it sends a "null message"
to the neighboring nodes, telling them that its clock has advanced, so that they
can update their own maximum date. And so on.

If this (short) explanation is not clear enough, feel free to Google the
algorithm name or check reference books such as [1].

>From a threading point of view, each thread (referred as Execution Units in the
code) runs a main loop, picking partitions from a runnable partitions pool and
running them until the simulation is finished.

Code changes
============

While implementing this simulator, I had to make some changes to other non
simulator-impl parts, changes which are listed below, with comments.

Intrusive changes
-----------------

* Added a /context/ attribute to events (read : EventKey and EventId objects),
  which is used to specify in which context the event should be processed. This
  is, for now, the id of the partition on which the event should be processed.

* Modified events ordering in the scheduler : events used to be ordered by
  (timestamp, uid), now they are ordered by (timestamp, context, uid).
  => This is used to avoid reordering traces in non-multithreaded simulations
     (to ensure consistency between threaded and non theaded implementations).

* Added a ScheduleWithContext function, which takes 1) a context parameter 2)
  the absolute Time at which the event should be processed 3) the usual Schedule
  parameters. This function does what its name tells : it schedules an event
  with a given context, while other Schedule functions just reuse the current
  simulation context (i.e. the context of the event currently being processed).
  => This is mostly used for initialization (for instance applications start)
     and in channels (where events such as packet arrival are scheduled on other
     nodes than the current one).
  => The time given to this function has to be absolute and not relative because
     the clock of the current partition might not be the same as the clock of
     the partition where the event is scheduled. Actually, I'm not sure this is
     still required. I'll have to investigate the issue again :)

* Added a bunch of Start () methods to MobilityModels, NetDevices and
  NetDeviceContainers, which are used to defer some initialization things to the
  beginning of the Simulator::Run (), such as initial beacon sending for
  wireless, in order to associate a context to every event.

* Added a GetMinDelay (Ptr<NetDevice> to) method to channels, which should
  return the minimum transmission delay to the given NetDevice from other
  NetDevices on the channel. This is used to compute the lookahead, and is
  cached when the partitions are created, that is, just before the first
  Simulator::Run () call.
  => This is only implemented for PointToPointChannels for now and ASSERT'd out
     for other channels. The definition of minimal delay is non-obvious for
     those other channels and is a discussion topic for this list.

* Changed a bunch of examples/unit tests to specify events context.
  => This is not really intrusive, but it shows that some user scripts may
     require changes, for instance if they kinda implement an application
     without using the application stuff (like in tcp-large-transfer).

* Forced initialization of a SimulatorSingletion in tcp-l4-protocol.cc.
  => This was required to prevent multiple initializations of the singleton due
     thread unsafety problems. The change in itself is not intrusive, but the
     problem is : Singletons have to be handled with care due to threading
     problems and restrictions must be clearly defined. List discussion topic,
     again.

Non intrusive changes
---------------------

* Added a MultiThreadingHelper, which is used to setup the required bits to use
  the multi-threaded simulator implementation.
  => Check multithreaded-udp-echo to know how to use it.

* Made Object, RefCountBase, Packet, CallbackImplBase classes ref/unref
  functions thread safe by locking appropriate mutexes.
  => This is a simple solution, but definitely not efficient. It can easily be
     replaced by picking thread-safe ref/unref implementations from other
     projects, such as gobject.

* Disabled Packet-related buffers/caches for thread-safety.
  => This issue will be investigated later (is re-enabling these buffers/caches
     worth the possible locking overhead ?).

Required (but not done yet) changes
-----------------------------------

* Rework CSMA channel to be able to correctly Schedule the reception events.
  Basically, I guess this means modifing CsmaChannel::TransmitEnd() and
  CsmaChannel::PropagationCompleteEvent() (which need some coding style love
  and typo fix btw, but that's off topic) to Schedule the
  PropagationCompleteEvent on each target node instead of globally. Comments
  appreciated.

Upcoming work
=============

Now that the implementation is mostly working, there are two obvious goals :

* Producing consistent simulation traces (i.e. the same traces as non threaded
  implementations), this should be mostly achieved by hacking the way the traces
  are produced, i.e. introducing something like an AsciiWriter and making it
  detect if post-simulation trace reordering is required plus hacking the
  PcapWriter.
* Performance (profiling, etc)

For those who would like to test the multithreaded simulator or check the
source, I've uploaded the code to [2].

Comments and bug reports appreciated :)

Regards,
Guillaume Seguin

[1] Parallel and Distributed Simulation Systems, from Richard M. Fujimoto
[2] http://code.nsnam.org/guillaume/ns-3-multithreading/