[Ns-developers] Proposed Simulator Changes

[craigdo@ee.washington.edu]

Hi all,

I sent out an email this past Wednesday outlining some changes I was
planning on making to the simulator to respond to some issues regarding
setting the simulation time based on the real-time clock.  I provided that
email at the end of this message for your convenience.

I have created a repository http://code.nsnam.org/craigdo/ns-3-rts that has
these changes implemented.  I also attached a patch to the bug I filed (#
376 -- http://www.nsnam.org/bugzilla/show_bug.cgi?id=376).

The approach is to make all of the familiar simulator schedule operations
have exactly the same semantics as they have all along (indistinguishable
from the case where there is no real-time clock living underneath).  The
upshot is that if you select the real-time simulator implementation:

  GlobalValue::Bind ("SimulatorImplementationType",
    StringValue ("ns3::RealtimeSimulatorImpl"));

Then you will get a system that attempts to pace the simulation time (as
defined completely be the non-real-time simulation implementation) to an
underlying real-time clock.  This should be sufficient for most people.
Your familiar methods:

  Simulator::Schedule ()
  Simulator::ScheduleNow ()
  Simulator::Now ()
 
all behave exactly as they do now, basing all of their timing on the current
simulation time which is set once at the start of event execution and does
not change until the start of the next event.  The simulator will basically
become a multi-threaded simulator that just paces events (introduces
real-time delays between events) with a system real-time clock.

There is a need to provide a way for external events to drive the simulation
time forward.  Since using a method that updates the simulation time based
on an underlying real-time clock is apparently like playing with fire, I
have taken these new methods and moved them behind a "firewall."  I have
created a new class called RealtimeSimulatorExtension (a friend of class
Simulator) that contains only the "dangerous" methods:

  RealtimeSimulatorExtension::ScheduleReal ()
  RealtimeSimulatorExtension::ScheduleRealNow ()
  RealtimeSimulatorExtension::RealNow ()

These are really for "experts" who know what they are doing and understand
why they have a need to use them.

- ScheduleReal() schedules an event for the current real time plus some
relative offset;
- ScheduleRealNow() schedules an event for the current real time;
- RealNow() returns the current real time.
 
Events scheduled using ScheduleReal() and ScheduleRealNow() will cause the
simulation time to change when they are executed.  You must not use these
schedule methods for any events that need to be temporally ordered since
ordering can change based on system load and kernel scheduling as described
in the bug report.  These are not discrete event methods -- time is
continuous there.  They should only be used for "external singleton events"
such as packet reception events on a device driver talking to the "real
world," and only by those folks that know what they're doing.

I've also made the Schedule methods explicitly use relative semantics all
the way down to the implementation code to allow atomic operation in
multithreaded environments.  Basically this just means moving the Now() +
time code from the Simulator class to the implementation classes.

Functionally, these changes preserve the original simulator methods and
semantics, so there's no API change even though a bit of plumbing has
changed.  I've added the three new methods that are currently unused, but
the real-time scheduling will be needed by an upcoming (for ns-3.3)
emulation feature addition.

Anyway, this may be a lot to digest, but I'd appreciate any input you may
have.

Regards,

-- Craig

> -----Original Message-----
> 
> 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 ----------
> 
> 
> 
>