[Ns-developers] Realtime Simulator Question

[craigdo@ee.washington.edu]

Hi all,

I just filed a bug against the real-time simulator regarding problems using
the real-time clock in ScheduleNow operations.  When I wrote this code, I
brought a mindset that came at the problem from the point of view of
external devices getting events generated on completely separate threads
queued for execution in the simulator at a certain real-time.

My initial approach, which was to unify simulation time and real-time by
essentially phase-locking them has turned out to cause some problems based
on model assumptions and also some fairly tricky timing issues that can
cause event ordering to change based on system load.  This is "Not Good"
(TM).  Something has got to change.

Rather than fixing this piecewise, I thought now would be good to put all of
my cards on the table, so to speak, and to solicit input on the API model I
plan to use to fix this issue.

The bug is #376 in the ns-3 tracker (reproduced below); and I think it has
enough information to make the problem and proposed solution clear.  To make
it explicit, though, currently we have:

  Schedule() -- schedule an event for some relative time in the future
  ScheduleNow() -- schedule an event for the current real time.

What I'm planning on doing is

  Schedule() -- schedule an event for some time in the future relative to
m_currentTs
  ScheduleNow() -- schedule an event for the current simulation time
(m_currentTs).
  ScheduleReal() -- schedule an event for some time in the future relative
to the current real time
  ScheduleRealNow() -- schedule an event for the current real time.

Having methods that set the simulation time are required since without them
it is possible to construct externally driven simulations for which
simulation time never advances.

In the new API, operations that involve possibly setting the simulation time
are broken out separately as ScheduleReal() and ScheduleRealNow().  If you
use Schedule() and ScheduleNow() your events are guaranteed to have
consistent ordering.  If you use ScheduleReal() and ScheduleRealNow() to
schedule related events, ordering may change based on system load as
described in the bug report.  I believe most people should use Schedule()
and ScheduleNow(), and only asynchronous external events should use
ScheduleReal() and ScheduleRealNow().

In the proposed API, the ordering of events scheduled by the
ScheduleReal{,Now} methods will have consistent order.  The events scheduled
by Schedule{,Now} will have consistent ordering.  Mixing scheduling methods
will have unpredictable results.

Do you think this is the way to go?  Am I missing anything?  Comments on the
names or where the new methods should go?  I have reproduced bug 376 below.

Regards,

-- Craig

---------- Begin Bug 376 ----------

Consider the following scenario (not using underlying real time clocks):

  Event A starts running at tA
  Schedule Event B for tA + tEpsilon
  long processing step tP consumes real-time tP
  ScheduleNow Event C

This would result in the following sequence of events:

  Event A, Event C, Event B

If you use ScheduleNow with an underlying realtime clock, and the time
consumed
by the the procesing step is small (tP < tEpsilon), the order of execution
is
unchanged.  However, if tP > tEpsilon the executed event order changes to

  Event A, Event B, Event C

In the real world tP may vary around tEpsilon and the event ordering may
change
unpredictably and incorrectly as system loads vary.

There are cases where doing a ScheduleNow using the actual underlying
realtime
clock is required (to cause simulation time to advance in the presence of
external events such as network packet reception).

There are cases where using the underlying real-time clock can cause errors
in
situations where dependent events can change order.

The current real-time simulator makes no distinction between scheduling
operations that involve the real-time clock and those that don't.  This
leads to
slippery situations.

There need to be two kinds of scheduling methods:  one set that respects
time
as models may assume using m_currentTs as a basis, and one set that works
with
the current real-time as a basis.  How this works is tricky.  The time to
process event A can no longer affect the order of the events A, B and C.  

If we implement a separate {Schedule, ScheduleNow} and {ScheduleReal,
ScheduleRealNow} the situation changes.  The related events {A,B,C} use
Schedule and ScheduleNow and are therefore using m_currentTs as a basis.
The
external device uses ScheduleRealNow and uses the current real-time as a
basis.

What we have then is an unrelated external event being scheduled for some
time
during the actual execution of the related events:

  Event A starts running at m_currentTs = tA, realtime ~ tA 
  Schedule() Event B for absolute time tA + tEpsilon (based on m_currentTs)
  long processing step consumes real-time during event A execution
  Packet Reception queues event D for realtime tA < tR < tEpsilon
  ScheduleNow Event C (based on m_currentTs) = tA

Here's what happens:

  1. Event A is run at about realtime = tA.
  2. Event B is inserted at the head of the queue for tA + tEpsilon
     at about realtime tA
  3. Event A continues running for some time tP.  Somewhere during the 
     event, an external thread schedules an event for 
     tA + tR (at the current realtime then) which is less than 
     tA + tEpsilon, so this goes at the head of the event queue.
  4. Event C is scheduled for m_currentTs = tA and so this goes
     to the head of the event queue.

  Event execution is as follows,

  Event A @ tA executes at realtime ~ tA
  Event C @ tA executes at realtime ~ tA plus tP (after event A)
  Event D @ tA + tR executes at realtime tA + tR
  Event B @ tA + tEpsilon

The order of the events A, B, C is preserved.  Event D is an unrelated
"asynchronous" event that happens at some realtime before tA + tEpsilon

You can see that if tA + tR > tA + tEpsilon (the reception event happens
during
the execution time of tA (where m_currentTs = tA) but at a realtime > tA +
tEpsilon, the execution order of all events changes, but the ordering of the
events scheduled by Schedule() and ScheduleNow() is preserved.

  Event A @ tA executes at realtime ~ tA
  Event C @ tA executes at realtime ~ tA plus tP (after event A)
  Event B @ tA + tEpsilon
  Event D @ tA + tR executes at realtime tA + tR

This seems to me to be the right thing to do.

---------- End Bug 376 ----------