\chapter{Network Dynamics}\label{chap:net-dynamics}This chapter describes the capabilities in \ns\to make the simulation topologies dynamic.We start with the instance procedures to the class Simulatorthat are \href{useful to a simulation script}{Section}{sec:userAPI}.The next section describes\href{the internal architecture}{Section}{sec:nd-internal-arch},including the different classes and instance variables and procedures;the following section describes\href{the interaction with unicast routing}{Section}{sec:unicast-int}.This aspect of network dynamics is still somewhat experimental in \ns.The last section of this chapter outlines some of\href{the deficiencies in the current realization}{Section}{sec:deficiencies}of network dynamics, some one or whichmay be fixed in the future.The procedures and functions described in this chapter can be found in\nsf{tcl/rtglib/dynamics.tcl} and \nsf{tcl/lib/route-proto.tcl}.\section{The user level API}\label{sec:userAPI}The user level interface to network dynamics is a collection of instance procedures in the class Simulator,and one procedure to trace and log the dynamics activity.Reflecting a rather poor choice of names,these procedures are\code{rtmodel}, \code{rtmodel-delete}, and \code{rtmodel-at}.There is one other procedure, \code{rtmodel-configure},that is used internally by the class Simulator to configurethe rtmodels just prior to simulation start.We describe this method \href{later}{Section}{sec:nd-internal-arch}.\begin{list}{---}{}\item The instance procedure\fcnref{\proc[]{rtmodel}}{../ns-2/dynamics.tcl}{Simulator::rtmodel}defines a model to be applied to the nodes and links in the topology.Some examples of this command as it would be used in a simulation script are:\begin{program}        $ns rtmodel Exponential {0.8 1.0 1.0} $n1        $ns rtmodel Trace dynamics.trc  $n2 $n3        $ns rtmodel Deterministic {20.0 20.0} $node(1) $node(5)\end{program}The procedure requires at least three arguments:\begin{itemize}\item % the model definitionThe first two arguments define the model that will be used, and theparameters to configure the model.The currently implemented models in \ns\ areExponential (On/Off), Deterministic (On/Off), Trace (driven), orManual (one-shot) models.\item % the parametersThe number, format, and interpretation of the configuration parametersis specific to the particular model.\begin{enumerate}\itemsep0pt\item The exponential on/off model takes four parameters:\tup{[start time], up interval, down interval, [finish time]}.\tup{start time} defaults to $0.5s.$ from the start of the simulation,\tup{finish time} defaults to the end of the simulation.\tup{up interval} and \tup{down interval} specifythe mean of the exponential distribution defining the timethat the node or link will be up and down respectively.The default up and down interval values are $10s.$ and $1s.$ respectively.Any of these values can be specified as ``$-$'' to default to theoriginal value.The following are example specifications of parameters to this model:\begin{program}      0.8 1.0 1.0       \; start at \(0.8s.\), up/down = \(1.0s.\), finish is default;      5.0 0.5           \; start is default, up/down = \(5.0s, 0.5s.\), finish is default;      - 0.7             \; start, up interval are default, down = \(0.7s.\), finish is default;      - - - 10          \; start, up, down are default, finish at \(10s.\);\end{program}\item The deterministic on/off modelis similar to the exponential model above, and  takes four parameters:\tup{[start time], up interval, down interval, [finish time]}.\tup{start time} defaults to the start of the simulation,\tup{finish time} defaults to the end of the simulation.Only the interpretation of the up and down interval is different;\tup{up interval} and \tup{down interval} specify the exact durationthat the node or link will be up and down respectively.The default values for these parameters are:\tup{start time} is $0.5s.$ from start of simulation,\tup{up interval} is $2.0s.$,\tup{down interval} is $1.0s.$, and\tup{finish time} is the duration of the simulation.\item The trace driven model takes one parameter:the name of the trace file.The format of the input trace file is identical to that output by the dynamics trace modules, \viz,\code{v \tup{time} link-\tup{operation} \tup{node1} \tup{node2}}.Lines that do not correspond to the node or link specified are ignored.{\small\begin{verbatim}        v 0.8123 link-up 3 5        v 3.5124 link-down 3 5\end{verbatim}}\item The manual one-shot model takes two parameters:the operation to be performed, and the time that it is to beperformed.\end{enumerate}\item % the elementsThe rest of the arguments to the \proc[]{rtmodel} proceduredefine the node or link that the model will be applied to.If only one node is specified,it is assumed that the node will fail.This is modeled by making the links incident on the node fail.If two nodes are specified, then the command assumes thatthe two are adjacent to each other, and the model is applied to thelink incident on the two nodes.If more than two nodes are specified, only the first is considered,the subsequent arguments are ignored.\item % \proc[]{rtmodel} will also enable tracing if the Simulator  instance variable, \code{traceAllFile_} is set.\end{itemize}The command returns the handle to the model that was created in this call.Internally, \proc[]{rtmodel} stores the list of route models createdin the class Simulator instance variable, \code{rtModel_}.\item The instance procedure\fcnref{\proc[]{rtmodel-delete}}{../ns-2/dynamics.tcl}{Simulator::rtmodel-delete}takes the handle of a route model as argument, removes it from the\code{rtModel_} list, and deletes the route model.\item The instance procedure\fcnref{\proc[]{rtmodel-at}}{../ns-2/dynamics.tcl}{Simulator::rtmodel-at}is a special interface to the Manual model of network dynamics.The command takes the time, operation, and node or link as arguments,and applies the operation to the node or link at the specified time.Example uses of this command are:\begin{program}        $ns rtmodel-at 3.5 up $n0        $ns rtmodel-at 3.9 up $n(3) $n(5)        $ns rtmodel-at 40  down  $n4\end{program}\end{list}Finally, the instance procedure \proc[]{trace-dynamics} of the class rtModelenables tracing of the dynamics effected by this model.It is used as:\begin{program}        set fh [open "dyn.tr" w]        $rtmodel1 trace-dynamics $fh        $rtmodel2 trace-dynamics $fh        $rtmodel1 trace-dynamics stdout\end{program}In this example, \code{$rtmodel1} writes out trace entries to bothdyn.tr and stdout; \code{$rtmodel2} only writes out trace entries to dyn.tr.A typical sequence of trace entries written out by either model might be:{\small\begin{verbatim}        v 0.8123 link-up 3 5        v 0.8123 link-up 5 3        v 3.5124 link-down 3 5        v 3.5124 link-down 5 3\end{verbatim}}These lines above indicate that Link~\tup{3, 5} failed at $0.8123s.$,and recovered at time $3.5124s.$\section{The Internal Architecture}\label{sec:nd-internal-arch}Each model of network dynamics is implemented as a separate class,derived from the base \clsref{rtModel}{../ns-2/dynamics.tcl}.We begin by describing\href{the base class rtModel and the derived classes}{Section}{sec:rtmodel}.The network dynamics models use an internal queuing structureto ensure that simultaneous events are correctly handled,the \clsref{rtQueue}{../ns-2/dynamics.tcl}.\href{The next subsection}{Section}{sec:rtqueue}describes the internals of this structure.Finally, we describe\href{the extensions to the existing classes}{Section}{sec:nd-extensions}:the Node, Link, and others.\subsection{The class rtModel}\label{sec:rtmodel}To use a new route model, the routine \proc[]{rtmodel}creates an instance of the appropriate type,defines the node or link that the model will operate upon,configures the model,and possibly enables tracing;The individual instance procedures that accomplish this in pieces are:\begin{list}{}{}\item The   \fcnref{constructor for the base class}{../ns-2/dynamics.tcl}{rtModel::init}  stores a reference to the Simulator in its instance variable, \code{ns_}.  It also initializes the \code{startTime_} and \code{finishTime_}  from the class variables of the same name.\item The instance procedure   \fcnref{set-elements}{../ns-2/dynamics.tcl}{rtModel::set-elements}  identifies the node or link that the model will operate upon.  The command stores two arrays: \code{links_}, of the links that the  model will act upon; \code{nodes_}, of the incident nodes  that will be affected by the link failure or recovery caused by the model.\item The default procedure in the base class   to set the model configuration parameters is  \fcnref{set-parms}{../ns-2/dynamics.tcl}{rtModel::set-parms}.  It assumes a well defined  start time, up interval, down interval, and a finish time,  and sets up configuration parameters for some class of models.  It stores these values in the instance variables:  \code{startTime_}, \code{upInterval_}, \code{downInterval_},  \code{finishTime_}.    The exponential and deterministic models use this default routine,  the trace based and manual models define their own procedures.\item % trace  The instance procedure  \fcnref{\proc[]{trace}}{../ns-2/dynamics.tcl}{rtModel::trace}  enables \proc[]{trace-dynamics} on each of the links that it affects.  Additional details on \proc[]{trace-dynamics} is discussed in the  \href{section on extensions to the class Link}{Section}{sec:nd-extensions}.\end{list}The next sequence of configuration steps are taken just prior tothe start of the simulator.\ns\ invokes \fcnref{\proc[]{rtmodel-configure}}{../ns-2/dynamics.tcl}{Simulator::rtmodel-configure}just before starting the simulation.This instance procedure first acquires an instance of the class rtQueue,and then invokes \proc[]{configure} for each route model in its list,\code{rtModel_}.\begin{list}{}{}\item The instance procedure  \fcnref{\proc[]{configure}}{../ns-2/dynamics.tcl}{rtModel::configure}  makes each link that is is applied to dynamic;  this is the set of links stored in its instance variable array,  \code{links_}.  Then the procedure schedules its first event.\item The default instance procedure  \fcnref{\proc[]{set-first-event}}{../ns-w/dynamics.tcl}{rtModel::set-first-event}  schedules the first event to take all the links ``down'' at \\  \code{$startTime_} + \code{upInterval_}.  Individual types of route models derived from this base class should  redefine tihs function.\item Two instance procedures in the base class ,  \fcnref{\proc[]{set-event}}{../ns-2/dynamics.tcl}{rtModel::set-event} and  \fcnref{\proc[]{set-event-exact}}{../ns-2/dynamics.tcl}{rtModel::set-event-exact},  can be used to schedule events in the route queue.  \proc[interval, operation]{set-event} schedules \code{operation}  after \code{interval} seconds from the current time; it uses the  procedure \proc[]{set-event-exact} below.  \proc[fireTime, operation]{set-event-exact} schedules \code{operation}  to execute at \code{fireTime}.  If the time for execution is greater than the \code{finishTime_},  then the only possible action is to take a failed link ``up''.\item  Finally, the base class provides the methods to take the links  \fcnref{\proc[]{up}}{../ns-2/dynamics.tcl}{rtModel::up} or  \fcnref{\proc[]{down}}{../ns-2/dynamics.tcl}{rtModel::down}.  Each method invokes the appropriate procedure on each of the links  in the instance variable, \code{links_}.\end{list}\paragraph{Exponential}The model schedules its first event to take the links downat \code{startTime_} + E(\code{upInterval_});It also defines the procedures, \proc[]{up} and \proc[]{down};each procedure invokes the base class procedure to perform the actual operation.This routine then reschedules the next event atE(\code{upInterval}) or E(\code{downInterval_}) respectively.\paragraph{Deterministic}The model defines the procedures, \proc[]{up} and \proc[]{down};each procedure invokes the base class procedure to perform the actual operation.This routine then reschedules the next event at\code{upInterval} or \code{downInterval_} respectively.\paragraph{Trace}The model redefines the instance procedure\fcnref{\proc[]{set-parms}}{../ns-2/dynamics.tcl}{rtModel/Trace::set-parms}to operan a trace file, and set events based on that input.The instance procedure\fcnref{\proc[]{get-next-event}}{../ns-2/dynamics.tcl}{rtModel/Trace::get-next-event}returns the next valid event from the trace file.A valid event is an event that is applicable to one of the links in this object's \code{links_} variable.The instance procedure\fcnref{\proc[]{set-trace-events}}{../ns-2/dynamics.tcl}{rtModel/Trace::set-trace-events}uses \proc[]{get-next-event}to schedule the next valid event.The model redefines\fcnref{\proc[]{set-first-event}}{../ns-2/dynamics.tcl}{rtModel/Trace::set-first-event},\fcnref{\proc[]{up}}{../ns-2/dynamics.tcl}{rtModel/Trace::up}, and