contrib/psg/src/peersim/edsim/EDSimulator.java

   1 /*
   2  * Copyright (c) 2003-2005 The BISON Project
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU Lesser General Public License version 2 as
   6  * published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU Lesser General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Lesser General Public License
  14  * along with this program; if not, write to the Free Software
  15  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16  *
  17  */
  18
  19 package peersim.edsim;
  20
  21 import java.util.Arrays;
  22
  23 import peersim.Simulator;
  24 import peersim.config.*;
  25 import peersim.core.*;
  26 import psgsim.PSGSimulator;
  27
  28 /**
  29  * Event-driven simulator engine. It is a fully static singleton class. For an
  30  * event driven simulation the configuration has to describe a set of
  31  * {@link Protocol}s, a set of {@link Control}s and their ordering and a set of
  32  * initializers and their ordering. See parameters {@value #PAR_INIT},
  33  * {@value #PAR_CTRL}.
  34  * <p>
  35  * One experiment run by {@link #nextExperiment} works as follows. First the
  36  * initializers are run in the specified order. Then the first execution of all
  37  * specified controls is scheduled in the event queue. This scheduling is
  38  * defined by the {@link Scheduler} parameters of each control component. After
  39  * this, the first event is taken from the event queue. If the event wraps a
  40  * control, the control is executed, otherwise the event is delivered to the
  41  * destination protocol, that must implement {@link EDProtocol}. This is
  42  * iterated while the current time is less than {@value #PAR_ENDTIME} or the
  43  * queue becomes empty. If more control events fall at the same time point, then
  44  * the order given in the configuration is respected. If more non-control events
  45  * fall at the same time point, they are processed in a random order.
  46  * <p>
  47  * The engine also provides the interface to add events to the queue. Note that
  48  * this engine does not explicitly run the protocols. In all cases at least one
  49  * control or initializer has to be defined that sends event(s) to protocols.
  50  * <p>
  51  * Controls can be scheduled (using the {@link Scheduler} parameters in the
  52  * configuration) to run after the experiment has finished. That is, each
  53  * experiment is finished by running the controls that are scheduled to be run
  54  * after the experiment.
  55  * <p>
  56  * Any control can interrupt an experiment at any time it is executed by
  57  * returning true in method {@link Control#execute}. However, the controls
  58  * scheduled to run after the experiment are still executed completely,
  59  * irrespective of their return value and even if the experiment was
  60  * interrupted.
  61  * <p>
  62  * {@link CDScheduler} has to be mentioned that is a control that can bridge the
  63  * gap between {@link peersim.cdsim} and the event driven engine. It can wrap
  64  * {@link peersim.cdsim.CDProtocol} appropriately so that the execution of the
  65  * cycles are scheduled in configurable ways for each node individually. In some
  66  * cases this can add a more fine-grained control and more realism to
  67  * {@link peersim.cdsim.CDProtocol} simulations, at the cost of some loss in
  68  * performance.
  69  * <p>
  70  * When protocols at different nodes send messages to each other, they might
  71  * want to use a model of the transport layer so that in the simulation message
  72  * delay and message omissions can be modeled in a modular way. This
  73  * functionality is implemented in package {@link peersim.transport}.
  74  *
  75  * @see Configuration
  76  */
  77 public class EDSimulator {
  78
  79         // ---------------------------------------------------------------------
  80         // Parameters
  81         // ---------------------------------------------------------------------
  82
  83         /**
  84          * The ending time for simulation. Only events that have a strictly smaller
  85          * value are executed. It must be positive. Although in principle negative
  86          * timestamps could be allowed, we assume time will be positive.
  87          *
  88          * @config
  89          */
  90         public static final String PAR_ENDTIME = "simulation.endtime";
  91
  92         /**
  93          * This parameter specifies how often the simulator should log the current
  94          * time on the standard error. The time is logged only if there were events
  95          * in the respective interval, and only the time of some actual event is
  96          * printed. That is, the actual log is not guaranteed to happen in identical
  97          * intervals of time. It is merely a way of seeing whether the simulation
  98          * progresses and how fast...
  99          *
 100          * @config
 101          */
 102         private static final String PAR_LOGTIME = "simulation.logtime";
 103
 104         /**
 105          * This parameter specifies the event queue to be used. It must be an
 106          * implementation of interface {@link PriorityQ}. If it is not defined, the
 107          * internal implementation is used.
 108          *
 109          * @config
 110          */
 111         private static final String PAR_PQ = "simulation.eventqueue";
 112
 113         /**
 114          * This is the prefix for initializers. These have to be of type
 115          * {@link Control}. They are run at the beginning of each experiment, in the
 116          * order specified by the configuration.
 117          *
 118          * @see Configuration
 119          * @config
 120          * @config
 121          */
 122         private static final String PAR_INIT = "init";
 123
 124         /**
 125          * This is the prefix for {@link Control} components. They are run at the
 126          * time points defined by the {@link Scheduler} associated to them. If some
 127          * controls have to be executed at the same time point, they are executed in
 128          * the order specified in the configuration.
 129          *
 130          * @see Configuration
 131          * @config
 132          */
 133         private static final String PAR_CTRL = "control";
 134
 135         // ---------------------------------------------------------------------
 136         // Fields
 137         // ---------------------------------------------------------------------
 138
 139         /** Maximum time for simulation */
 140         private static long endtime;
 141
 142         /** Log time */
 143         private static long logtime;
 144
 145         /** holds the modifiers of this simulation */
 146         private static Control[] controls = null;
 147
 148         /** Holds the control schedulers of this simulation */
 149         private static Scheduler[] ctrlSchedules = null;
 150
 151         /** Ordered list of events (heap) */
 152         private static PriorityQ heap = null;
 153
 154         private static long nextlog = 0;
 155
 156         // =============== initialization ======================================
 157         // =====================================================================
 158
 159         /** to prevent construction */
 160         private EDSimulator() {
 161         }
 162
 163         // ---------------------------------------------------------------------
 164         // Private methods
 165         // ---------------------------------------------------------------------
 166
 167         /**
 168          * Load and run initializers.
 169          */
 170         private static void runInitializers() {
 171
 172                 Object[] inits = Configuration.getInstanceArray(PAR_INIT);
 173                 String names[] = Configuration.getNames(PAR_INIT);
 174
 175                 for (int i = 0; i < inits.length; ++i) {
 176
 177                         System.err.println("- Running initializer " + names[i] + ": "
 178                                         + inits[i].getClass());
 179                         ((Control) inits[i]).execute();
 180                 }
 181         }
 182
 183         // --------------------------------------------------------------------
 184
 185         private static void scheduleControls() {
 186                 // load controls
 187                 String[] names = Configuration.getNames(PAR_CTRL);
 188                 controls = new Control[names.length];
 189                 ctrlSchedules = new Scheduler[names.length];
 190                 for (int i = 0; i < names.length; ++i) {
 191                         controls[i] = (Control) Configuration.getInstance(names[i]);
 192                         ctrlSchedules[i] = new Scheduler(names[i], false);
 193                 }
 194                 System.err.println("EDSimulator: loaded controls "
 195                                 + Arrays.asList(names));
 196
 197                 // Schedule controls execution
 198                 if (controls.length > heap.maxPriority() + 1)
 199                         throw new IllegalArgumentException("Too many control objects");
 200                 for (int i = 0; i < controls.length; i++) {
 201                         new ControlEvent(controls[i], ctrlSchedules[i], i);
 202                 }
 203         }
 204
 205         // ---------------------------------------------------------------------
 206
 207         /**
 208          * Adds a new event to be scheduled, specifying the number of time units of
 209          * delay, and the execution order parameter.
 210          *
 211          * @param time
 212          *            The actual time at which the next event should be scheduled.
 213          * @param order
 214          *            The index used to specify the order in which control events
 215          *            should be executed, if they happen to be at the same time,
 216          *            which is typically the case.
 217          * @param event
 218          *            The control event
 219          */
 220         static void addControlEvent(long time, int order, ControlEvent event) {
 221                 // we don't check whether time is negative or in the past: we trust
 222                 // the caller, which must be from this package
 223                 if (time >= endtime)
 224                         return;
 225                 heap.add(time, event, null, (byte) 0, order);
 226         }
 227
 228         // ---------------------------------------------------------------------
 229
 230         /**
 231          * This method is used to check whether the current configuration can be
 232          * used for event driven simulations. It checks for the existence of config
 233          * parameter {@value #PAR_ENDTIME}.
 234          */
 235         public static final boolean isConfigurationEventDriven() {
 236                 return Configuration.contains(PAR_ENDTIME);
 237         }
 238
 239         // ---------------------------------------------------------------------
 240
 241         /**
 242          * Execute and remove the next event from the ordered event list.
 243          *
 244          * @return true if the execution should be stopped.
 245          */
 246         private static boolean executeNext() {
 247                 PriorityQ.Event ev = heap.removeFirst();
 248                 if (ev == null) {
 249                         System.err.println("EDSimulator: queue is empty, quitting"
 250                                         + " at time " + CommonState.getTime());
 251                         return true;
 252                 }
 253
 254                 long time = ev.time;
 255
 256                 if (time >= nextlog) {
 257                         // System.err.println("Current time: " + time);
 258                         // seemingly complicated: to prevent overflow
 259                         while (time - nextlog >= logtime)
 260                                 nextlog += logtime;
 261                         if (endtime - nextlog >= logtime)
 262                                 nextlog += logtime;
 263                         else
 264                                 nextlog = endtime;
 265                 }
 266                 if (time >= endtime) {
 267                         System.err.println("EDSimulator: reached end time, quitting,"
 268                                         + " leaving " + heap.size()
 269                                         + " unprocessed events in the queue");
 270                         return true;
 271                 }
 272
 273                 CommonState.setTime(time);
 274                 int pid = ev.pid;
 275                         if (ev.node == null) {
 276                         // might be control event; handled through a special method
 277                         ControlEvent ctrl = null;
 278                         try {
 279                                 ctrl = (ControlEvent) ev.event;
 280                         } catch (ClassCastException e) {
 281                                 throw new RuntimeException(
 282                                                 "No destination specified (null) for event " + ev);
 283                         }
 284                         return ctrl.execute();
 285                 } else if (ev.node != Network.prototype && ev.node.isUp()) {
 286                         CommonState.setPid(pid);
 287                         CommonState.setNode(ev.node);
 288                         if (ev.event instanceof NextCycleEvent) {
 289                                 NextCycleEvent nce = (NextCycleEvent) ev.event;
 290                                 nce.execute();
 291                         } else {
 292                                 EDProtocol prot = null;
 293                                 try {
 294                                         prot = (EDProtocol) ev.node.getProtocol(pid);
 295                                         // System.out.println("prot "+prot.getClass().getName());
 296                                 } catch (ClassCastException e) {
 297                                         e.printStackTrace();
 298                                         throw new IllegalArgumentException("Protocol "
 299                                                         + Configuration.lookupPid(pid)
 300                                                         + " does not implement EDProtocol; "
 301                                                         + ev.event.getClass());
 302                                 }
 303                                 prot.processEvent(ev.node, pid, ev.event);
 304                         }
 305                 }
 306
 307                 return false;
 308         }
 309
 310         // ---------------------------------------------------------------------
 311         // Public methods
 312         // ---------------------------------------------------------------------
 313
 314         /**
 315          * Runs an experiment, resetting everything except the random seed.
 316          */
 317         public static void nextExperiment() {
 318                 // Reading parameter
 319                 if (Configuration.contains(PAR_PQ))
 320                         heap = (PriorityQ) Configuration.getInstance(PAR_PQ);
 321                 else
 322                         heap = new Heap();
 323                 endtime = Configuration.getLong(PAR_ENDTIME);
 324                 if (CommonState.getEndTime() < 0) // not initialized yet
 325                         CommonState.setEndTime(endtime);
 326                 if (heap.maxTime() < endtime)
 327                         throw new IllegalParameterException(PAR_ENDTIME,
 328                                         "End time is too large: configured event queue only"
 329                                                         + " supports " + heap.maxTime());
 330                 logtime = Configuration.getLong(PAR_LOGTIME, Long.MAX_VALUE);
 331
 332                 // initialization
 333                 System.err.println("EDSimulator: resetting");
 334                 CommonState.setPhase(CommonState.PHASE_UNKNOWN);
 335                 CommonState.setTime(0); // needed here
 336                 controls = null;
 337                 ctrlSchedules = null;
 338                 nextlog = 0;
 339                 Network.reset();
 340                 System.err.println("EDSimulator: running initializers");
 341                 runInitializers();
 342                 scheduleControls();
 343                         // Perform the actual simulation; executeNext() will tell when to
 344                 // stop.
 345                 boolean exit = false;
 346                 while (!exit) {
 347                         exit = executeNext();
 348                 }
 349
 350                 // analysis after the simulation
 351                 CommonState.setPhase(CommonState.POST_SIMULATION);
 352                 for (int j = 0; j < controls.length; ++j) {
 353                         if (ctrlSchedules[j].fin)
 354                                 controls[j].execute();
 355                 }
 356
 357         }
 358
 359         // ---------------------------------------------------------------------
 360
 361         /**
 362          * Adds a new event to be scheduled, specifying the number of time units of
 363          * delay, and the node and the protocol identifier to which the event will
 364          * be delivered.
 365          *
 366          * @param delay
 367          *            The number of time units before the event is scheduled. Has to
 368          *            be non-negative.
 369          * @param event
 370          *            The object associated to this event
 371          * @param node
 372          *            The node associated to the event.
 373          * @param pid
 374          *            The identifier of the protocol to which the event will be
 375          *            delivered
 376          */
 377         public static void add(long delay, Object event, Node node, int pid) {
 378                 //if (event instanceof NextCycleEvent)
 379                         //System.err.println("************* edsim delay="+delay +" pid="+pid+" event="+event+" time="+CommonState.getTime());
 380                 if (Simulator.getSimID() == 2){
 381                         PSGSimulator.add(delay, event, node, pid);
 382                 }
 383
 384                 else {
 385                         if (delay < 0)
 386                                 throw new IllegalArgumentException("Protocol "
 387                                                 + node.getProtocol(pid) + " is trying to add event "
 388                                                 + event + " with a negative delay: " + delay);
 389                         if (pid > Byte.MAX_VALUE)
 390                                 throw new IllegalArgumentException(
 391                                                 "This version does not support more than "
 392                                                                 + Byte.MAX_VALUE + " protocols");
 393
 394                         long time = CommonState.getTime();
 395                         if (endtime - time > delay) // check like this to deal with overflow
 396                                 heap.add(time + delay, event, node, (byte) pid);
 397                 }
 398         }
 399
 400 }