srm.tex

柯老师网站上找到的

possibly creating that object, if it did not already exist.
The \clsref{SRMinfo}{../ns-2/srm-state.h} has two methods
to access and set the bit vector, \ie,
\begin{alist}
\fcn[int id]{ifReceived} & indicates whether the particular message
                from the appropriate sender, with id \code{id}
                 was received at $n_i$,\\
\fcn[int id]{setReceived} & to set the bit to indicate that the
                particular message from the appropriate sender,
                with id \code{id} was received at $n_i$.
\end{alist}
The session message variables to access timing information are public;
no encapsulating methods are provided.  These are:
\begin{program}
        int     lsess_;                   \* # of last session msg received */
        int     sendTime_;                \* Time sess. msg. # sent */
        int     recvTime_;                \* Time sess. msg. # received */
        double  distance_;

        /* {\cf Data messages} */
        int     ldata_;                   \* # of last data msg sent */
\end{program}

\section{Loss Recovery Objects}
\label{sec:recovery}

In the last section,
we described the agent behavior when it receives a message.
Timers are used to control when any particular control message is to be sent.
The SRM agent uses a separate
\clsref{SRM}{../ns-2/srm.tcl}
to do the timer based processing.
In this section, we describe the basics if the class SRM,
and the loss recovery objects.
The following section will describe how the class SRM is used 
for sending periodic session messages.
An SRM agent will instantiate one object to recover from one lost data packet.
Agents that detect the loss will instantiate an object in the
\clsref{SRM/request}{../ns-2/srm.tcl};
agents that receive a request and have the required data will
instantiate an object in the \clsref{SRM/repair}{../ns-2/srm.tcl}.

\paragraph{Request Mechanisms}
SRM agents detect loss when they receive a message, and
infer the loss based on the sequence number on the message received.
Since packet reception is handled entirely by the compiled object,
loss detection occurs in the C++ methods.
Loss recovery, however, is handled entirely by instance procedures
of the corresponding interpreted object in OTcl.

When any of the methods detects new losses, it invokes
\fcnref{\proc[]{Agent/SRM::request}}{../ns-2/srm.tcl}{Agent/SRM::request}
with a list of the message sequence numbers that are missing.
\proc[]{request} will create a new \code{requestFunction_}
object for each message that is missing.
The agent stores the object handle in its array of \code{pending_} objects.
The key to the array is the message identifier \tup{sender}:\tup{msgid}.
\begin{list}{}{}
\item 
  The default \code{requestFunction_} is \clsref{SRM/request}.
  The constructor for the class SRM/request
  calls the base class constructor to initialize 
  the simulator instance (\code{ns_}), the SRM agent (\code{agent_}),
  trace file (\code{trace_}), and the \code{times_} array.
  It then initializes its \code{statistics_} array with the pertinent elements.

\item
  A separate call to
  \fcnref{\proc[]{set-params}}{../ns-2/srm.tcl}{SRM::set-params}
  sets the \code{sender_}, \code{msgid_}, \code{round_} instance variables for
  the request object.
  The object determines \code{C1_} and \code{C2_} by querying its \code{agent_}.
  It sets its distance to the sender (\code{times_(distance)})
  and fixes other scheduling parameters:
  the backoff constant (\code{backoff_}),
  the current number of backoffs (\code{backoffCtr_}),
  and the limit (\code{backoffLimit_}) fixed by the agent.
  \proc[]{set-params} writes the trace entry ``\textsc{q detect}''.

\item
  The final step in \proc[]{request} is to schedule the timer
  to send the actual request at the appropriate moment.
  The instance procedure
  \fcnref{\proc[]{SRM/request::schedule}}{../ns-2/srm.tcl}{%
    SRM/request::schedule}
  uses 
  \fcnref{\proc[]{compute-delay}}{%
    ../ns-2/srm.tcl}{SRM/request::compute-delay}
  and its current backoff constant to determine the delay.
  The object schedules
  \fcnref{\proc[]{send-request}}{../ns-2/srm.tcl}{SRM/request::send-request}
  to be executed after \code{delay_} seconds.
  The instance variable \code{eventID_} stores a handle to the scheduled event.
  The default \proc[]{compute-delay} function returns a value
  uniformly distributed in the interval $[C_1 d_s, (C_1 + C_2) d_s]$,
  where $d_s$ is twice \code{$times_(distance)}.
  The \proc[]{schedule} schedules an event to send a request
  after the computed delay. 
  The routine writes a trace entry ``\textsc{q ntimer } at \tup{time}''.
\end{list}

When the scheduled timer fires, the routine
\fcnref{\proc[]{send-request}}{../ns-2/srm.tcl}{SRM/request::send-request}
sends the appropriate message.
It invokes ``\code{$agent_} send request \tup{args}'' to send the request.
Note that \proc[]{send} is an instproc-like,
executed by the \fcn[]{command} method of the compiled object.
However, it is possible to overload the instproc-like
with a specific instance procedure \proc[]{send}
for specific configurations.
As an example, recall that the file \code{tcl/mcast/srm-nam.tcl}
overloads the \proc[]{send} command
to set the flowid based on type of message that is sent.
\proc[]{send-request} updates the statistics, and writes the trace entry
``\textsc{q sendnack}''.

When the agent receives a control message for a packet
for which a pending object exists,
the agent will hand the message off to the object for processing.
\begin{list}{}{}
\item When a 
  \fcnref{request for a particular packet is received}{../ns-2/srm.tcl}{%
        SRM/request::recv-request},
  the request object can be in one of two states:
  it is ignoring requests, considering them to be duplicates, or
  it will cancel its send event and re-schedule another one,
  after having backed off its timer.
  If ignoring requests it will update its statistics,
  and write the trace entry ``\textsc{q nack } dup''.
  Otherwise, set a time based on its current estimate of the \code{delay_},
  until which to ignore further requests.
  This interval is marked by the instance variable \code{ignore_}.
  If the object reschedules its timer, it will write the trace entry
  ``\textsc{ q nack ignore-backoff } \tup{ignore}''.
  Note that this re-scheduling relies on the fact that
  the agent has joined the multicast group, and will therefore
  receive a copy of every message it sends out.
  
\item When the
  \fcnref{request object receives a repair for the particular packet}{%
    ../ns-2/srm.tcl}{SRM/request::recv-repair},
  it can be in one of two states:
  either it is still waiting for the repair,
  or it has already received an earlier repair.
  If it is the former, there will be an event pending
  to send a request, and \code{eventID_} will point to that event.
  The object will compute its serviceTime, cancel that event,
  and set a hold-down period during which it will ignore 
  other requests.
  At the end of the hold-down period, the object will ask its
  agent to clear it.
  It will write the trace entry ``\textsc{q repair ignores } \tup{ignore}''.
  On the other hand, if this is a duplicate repair,
  the object will update its statistics, and write the trace entry
  ``\textsc{q repair } dup''.
\end{list}

When the loss recovery phase is completed by the object,
\fcnref{\proc[]{Agent/SRM::clear}}{../ns-2/srm.tcl}{Agent/SRM::clear}
will remove the object from its array of \code{pending_} objects,
and place it in its list of \code{done_} objects.
Periodically, the agent will cleanup and delete the \code{done_} objects.

\paragraph{Repair Mechanisms}
The agent will initiate a repair if it receives a request for a packet,
and it does not have a request object \code{pending_} for that packet.
The default repair object belongs to the
\clsref{SRM/repair}{../ns-2/srm.tcl}.
Barring minor differences,
the sequence of events and the instance procedures in this class
are identical to those for SRM/request.
Rather than outline every single procedure, we only outline
the differences from those described earlier for a request object.

The repair object uses the repair parameters, \code{D1_}, \code{D2_}.
A repair object does not repeatedly reschedule is timers;
therefore, it does not use any of the backoff variables
such as that used by a request object.
The repair object ignores all requests for the same packet.
The repair objet does not use the \code{ignore_} variable that
request objects use.
The trace entries written by repair objects are marginally different;
they are ``\textsc{p nack } from \tup{requester}'',
``\textsc{p rtimer } at \tup{fireTime}'',
``\textsc{p sendrep}'', ``\textsc{p repair ignores } \tup{holddown}''.

Apart from these differences,
the calling sequence for events in a repair object is similar to that
of a request object.

\paragraph{Mechanisms for Statistics}
The agent, in concert with the request and repair objects, 
collect statistics about their response to data loss \cite{Floy95:Reliable}.
Each call to the agent \proc[]{request} procedure marks a new period.
At the start of a new period,
\fcnref{\proc[]{mark-period}}{../ns-2/srm.tcl}{Agent/SRM::mark-period}
computes the moving average of the number of duplicates in the last period.
Whenever the agent receives a first round request from another agent,
and it had sent a request in that round, then it considers the request
as a duplicate request, and increments the appropriate counters.
A request object does not consider duplicate requests if it did not
itself send a request in the first round. 
If the agent has a repair object pending, then it does not consider
the arrival of duplicate requests for that packet.
The object methods
\fcnref{\proc[]{SRM/request::dup-request?}}{../ns-2/srm.tcl}{%
        SRM/request::dup-request?} and
\fcnref{\proc[]{SRM/repair::dup-request?}}{../ns-2/srm.tcl}{%
        SRM/repair::dup-request?} 
encode these policies, and return 0 or 1 as required.

A request object also computes the elapsed time between 
when the loss is detected to when it receives the first request.
The agent computes a moving average of this elapsed time.
The object computes the elapsed time (or delay) when it
\fcnref{cancels}{../ns-2/srm.tcl}{SRM/request::cancel}
its scheduled event for the first round.
The object invokes
\fcnref{Agent/SRM::update-ave}{../ns-2/srm.tcl}{Agent/SRM::update-ave}
to compute the moving average of the delay.

The agent keeps similar statistics of the duplicate repairs,
and the repair delay.

The agent stores the number of rounds taken for one loss recovery,
to ensure that subsequent loss recovery phases for that packet
that are not definitely not due to data loss
do not account for these statistics.
The agent stores the number of routes taken for a phase in
the array \code{old_}.
When a new loss recovery object is instantiated,
the object will use the agent's instance procedure
\fcnref{\proc[]{round?}}{../ns-2/srm.tcl}{Agent/SRM::round?}
to determine the number of rounds in a previous loss recovery phase
for that packet.

\section{Session Objects}
\label{sec:session}

Session objects,
\href{like the loss recovery objects}{Section}{sec:recovery},
are derived from the base \clsref{SRM}.
Unlike the loss recovery objects though,
the agent only creates one session object for the lifetime of the agent.
The constructor invokes the base class constructor as before;
it then sets its instance variable \code{sessionDelay_}.
The agent creates the session object when it \proc[]{start}s.
At that time, it also invokes
\fcnref{SRM/session::schedule}{../ns-2/srm.tcl}{SRM/session::schedule},
to send a session message after \code{sessionDelay_} seconds.

When the object sends a session message,
it will schedule to send the next one after some interval.
It will also update its statistics.
\fcnref{\proc[]{send-session}}{../ns-2/srm.tcl}{SRM/session::send-session}
writes out the trace entry ``\textsc{s session}''.

The class overrides the
\proc[]{evTrace} routine that writes out the trace entries.
\fcnref{SRM/session::evTrace}{../ns-2/srm.tcl}{SRM/sesion::evTrace}
disable writing out the trace entry for session messages.

Two types of session message scheduling strategies are currently
available:
The function in the base class schedules sending session messages at
fixed intervals of \code{sessionDelay_} jittered around a small value
to avoid synchronization among all the agents at all the nodes.
\clsref{SRM/session/logScaled} schedules sending messages
at intervals of \code{sessionDelay} times $\log_2$(\code{groupSize_})
so that the frequency of session messages is inversely proportional to 
the size of the group.

The base class that sends messages at fixed intervals
is the default \code{sessionFunction_} for the agent.

\section{Extending the Base Class Agent}
\label{sec:extensions}

In
\href{the earlier section on configuration parameters}{Section}{sec:config-param},
we had shown how to trivially extend the agent to
get deterministic and probabilistic protocol behavior.
In this section, we describe how to derive more complex
extensions to the protocol for fixed and adaptive timer mechanisms.

\subsection{Fixed Timers}

The fixed timer mechanism are done in
the derived \clsref{Agent/SRM/Fixed}.
The main difference with fixed timers is that
the repair parameters are set to $\log$(\code{groupSize_}).
Therefore, 
\fcnref{the repair procedure of a fixed timer agent}{../ns-2/srm.tcl}{%
        Agent/SRM/Fixed::repair}
will set \d1 and \d2 to be proportional to the group size
before scheduling the repair object.