srm.tex

柯老师网站上找到的

  returns the agent's current estimate of the multicast group size.
\item
  \fcnref{\proc[]{distances?}}{../ns-2/srm.cc.html}{SRMAgent::command}
  returns a list of key-value pairs of distances;
  the key is the address of the agent, 
  the value is the estimate of the distance to that agent.
  The first element is the address of this agent, and the distance of 0.
\item
  \fcnref{\proc[]{distance?}}{../ns-2/srm.cc.html}{SRMAgent::command}
  returns the distance to the particular agent specified as argument.

  The default distance at the start of any simulation is 1.
\end{list}
\begin{program}
        $srm(i) groupSize?    \; returns $srm(i)'s estimate of the group size;
        $srm(i) distances?    \; returns list of \tup{address, distance} tuples;
        $srm(i) distance? 257 \; returns the distance to agent at address 257;
\end{program}

\subsection{Tracing}
Each object writes out trace information that can be used to track the
progress of the object in its error recovery.
Each trace entry is of the form:
\begin{program}
\tup{prefix} \tup{tag} \tup{type of entry} \tup{values}
\end{program}
The prefix is as describe in the previous section for statistics.
The tag is {\bf Q} for request objects, {\bf P} for repair objects, and
{\bf S} for session objects.
The following types of trace entries and parameters are written by each
object:

\centerline{\small\renewcommand{\arraystretch}{1.3}
\begin{tabular}{rclp{2in}}\hline
      & Type of &              & \\
  Tag & Object  & Other values & Comments\\ \hline
  Q & DETECT & & \\
  Q & INTERVALS & C1 \tup{C1\_} C2 \tup{C2\_} dist \tup{distance} i \tup{backoff\_} & \\
  Q & NTIMER & at \tup{time} & Time the request timer will fire \\
  Q & SENDNACK & & \\
  Q & NACK & IGNORE-BACKOFF \tup{time} & Receive NACK, ignore other NACKs until
  \tup{time} \\
  Q & REPAIR & IGNORES \tup{time} & Receive REPAIR, ignore NACKs until \tup{time}  \\
  Q & DATA & & Agent receives data instead of repair.  Possibly indicates out of order arrival of data. \\ \hline
  P & NACK & from \tup{requester} & Receive NACK, initiate repair \\
  P & INTERVALS & D1 \tup{D1\_} D2 \tup{D2\_} dist \tup{distance} & \\
  P & RTIMER & at \tup{time} & Time the repair timer will fire \\
  P & SENDREP & \\
  P & REPAIR & IGNORES \tup{time} & Receive REPAIR, ignore NACKs until \tup{time} \\
  P & DATA & & Agent receives data instead of repair.  Indicates premature request by an agent. \\ \hline
  S & SESSION & & logs session message sent \\ \hline
\end{tabular}}
The following illustrates a typical trace for a single loss and recovery.
{\small
\begin{verbatim}
 3.5543 n 1 m <1:1> r 0 Q DETECT
 3.5543 n 1 m <1:1> r 1 Q INTERVALS C1 2.0 C2 0.0 d 0.0105 i 1
 3.5543 n 1 m <1:1> r 1 Q NTIMER at 3.57527
 3.5685 n 2 m <1:1> r 0 Q DETECT
 3.5685 n 2 m <1:1> r 1 Q INTERVALS C1 2.0 C2 0.0 d 0.021 i 1
 3.5685 n 2 m <1:1> r 1 Q NTIMER at 3.61053
 3.5753 n 1 m <1:1> r 1 Q SENDNACK
 3.5753 n 1 m <1:1> r 2 Q INTERVALS C1 2.0 C2 0.0 d 0.0105 i 2
 3.5753 n 1 m <1:1> r 2 Q NTIMER at 3.61727
 3.5753 n 1 m <1:1> r 2 Q NACK IGNORE-BACKOFF 3.59627
 3.5828 n 3 m <1:1> r 0 Q DETECT
 3.5828 n 3 m <1:1> r 1 Q INTERVALS C1 2.0 C2 0.0 d 0.032 i 1
 3.5828 n 3 m <1:1> r 1 Q NTIMER at 3.6468
 3.5854 n 0 m <1:1> r 0 P NACK from 257
 3.5854 n 0 m <1:1> r 1 P INTERVALS D1 1.0 D2 0.0 d 0.0105
 3.5854 n 0 m <1:1> r 1 P RTIMER at 3.59586
 3.5886 n 2 m <1:1> r 2 Q INTERVALS C1 2.0 C2 0.0 d 0.021 i 2
 3.5886 n 2 m <1:1> r 2 Q NTIMER at 3.67262
 3.5886 n 2 m <1:1> r 2 Q NACK IGNORE-BACKOFF 3.63062
 3.5959 n 0 m <1:1> r 1 P SENDREP
 3.5959 n 0 m <1:1> r 1 P REPAIR IGNORES 3.62736
 3.5971 n 4 m <1:1> r 0 Q DETECT
 3.5971 n 4 m <1:1> r 1 Q INTERVALS C1 2.0 C2 0.0 d 0.0425 i 1
 3.5971 n 4 m <1:1> r 1 Q NTIMER at 3.68207
 3.5971 n 5 m <1:1> r 0 Q DETECT
 3.5971 n 5 m <1:1> r 1 Q INTERVALS C1 2.0 C2 0.0 d 0.042 i 1
 3.5971 n 5 m <1:1> r 1 Q NTIMER at 3.68107
 3.6029 n 3 m <1:1> r 2 Q INTERVALS C1 2.0 C2 0.0 d 0.032 i 2
 3.6029 n 3 m <1:1> r 2 Q NTIMER at 3.73089
 3.6029 n 3 m <1:1> r 2 Q NACK IGNORE-BACKOFF 3.66689
 3.6102 n 1 m <1:1> r 2 Q REPAIR IGNORES 3.64171
 3.6172 n 4 m <1:1> r 2 Q INTERVALS C1 2.0 C2 0.0 d 0.0425 i 2
 3.6172 n 4 m <1:1> r 2 Q NTIMER at 3.78715
 3.6172 n 4 m <1:1> r 2 Q NACK IGNORE-BACKOFF 3.70215
 3.6172 n 5 m <1:1> r 2 Q INTERVALS C1 2.0 C2 0.0 d 0.042 i 2
 3.6172 n 5 m <1:1> r 2 Q NTIMER at 3.78515
 3.6172 n 5 m <1:1> r 2 Q NACK IGNORE-BACKOFF 3.70115
 3.6246 n 2 m <1:1> r 2 Q REPAIR IGNORES 3.68756
 3.6389 n 3 m <1:1> r 2 Q REPAIR IGNORES 3.73492
 3.6533 n 4 m <1:1> r 2 Q REPAIR IGNORES 3.78077
 3.6533 n 5 m <1:1> r 2 Q REPAIR IGNORES 3.77927
\end{verbatim}
}
The logging of request and repair traces is done by
\fcnref{\proc[]{SRM::evTrace}}{../ns-2/srm.tcl}{SRM::evTrace}.
However, the routine
\fcnref{\proc[]{SRM/Session::evTrace}}{../ns-2/srm.tcl}{SRM/Session::evTrace},
overrides the base class definition of \proc[]{srm::evTrace},
and writes out nothing.
Individual simulation scripts can override these methods
for greater flexibility in logging options.
One possible reason to override these methods might to
reduce the amount of data generated;
the new procedure could then generate compressed and processed output.

Notice that the trace filoe contains sufficient information and details
to derive most of the statistics written out in the log file, or
is stored in the statistics arrays.

\section{Architecture and Internals}
\label{sec:architecture}

The SRM agent implementation splits the protocol functions
into packet handling, loss recovery, and session message activity.
\begin{list}{}{}
\item  Packet handling consists of forwarding application data messages,
  sending and receipt of control messages.
  These activities are executed by C++ methods.
\item  Error detection is done in C++ due to receipt of messages.
  However, the loss recovery is entirely done through 
  instance procedures in OTcl.
\item  The sending and processing of messages is accomplished in C++;
  the policy about when these messages should be sent is decided
  by instance procedures in OTcl.
\end{list}
We first describe the C++
\href{processing due to receipt of messages}{Section}{sec:receipt}.
Loss recovery and the sending of session messages involves
timer based processing.
The agent uses a separate \clsref{SRM}{../ns-2/srm.tcl}
to perform the timer based functions.
For each loss, an agent may do either request or repair processing.
Each agent will instantiate a separate loss recovery object
for every loss, as is appropriate for the processing that it has to do.
In the following section
\href{we describe the basic timer based functions and
the loss recovery mechanisms}{Section}{sec:recovery}.
Finally, each agent uses one timer based function
for \href{sending periodic session messages}{Section}{sec:session}.

\section{Packet Handling: Processing received messages}
\label{sec:receipt}

The
\fcnref{\fcn[]{recv}}{../ns-2/srm.cc}{SRMAgent::recv}
method can receive four type of messages:
data, request, repair, and session messages.

\paragraph{Data Packets}
The agent does not generate any data messages.
The user has to specify an external agent to generate traffic.
The \fcn[]{recv} method must distinguish between
locally originated data that must be sent to the multicast group,
and data received from multicast group that must be processed.
Therefore, the application agent must
set the packet's destination address to zero.

For locally originated data, 
the agent adds the appropriate SRM headers,
sets the destination address to the multicast group, 
and forwards the packet to its target.

On receiving a data message from the group,
\fcnref{\fcn[sender, msgid]{recv\_data}}{../ns-2/srm.cc}{SRMAgent::recv\_data}
will update its state marking message \tup{sender, msgid} received,
and possibly trigger requests if it detects losses.
In addition, if the message was an older message received out of order,
then there must be a pending request or repair that must be cleared.
In that case, the compiled object invokes the OTcl instance procedure,
\fcnref{\proc[sender, msgid]{recv-data}}{%
  ../ns-2/srm.tcl}{Agent/SRM::recv-data}%
\footnote{Technically,
  \fcn[]{recv\_data} invokes the instance procedure
  \code{recv data \tup{sender} \tup{msgid}},
  that then invokes \proc[]{recv-data}.
  The indirection allows individual simulation scripts to override the
  \proc[]{recv} as needed.}.

Currently, there is no provision for the receivers
to actually receive any application data.
The agent does not also store any of the user data.
It only generates repair messages of the appropriate size,
defined by the instance variable \code{packetSize_}.
However, the agent assumes that any application data
is placed in the data portion of the packet,
pointed to by \code{packet->accessdata()}.

\paragraph{Request Packets}
On receiving a request, 
\fcnref{\fcn[sender, msgid]{recv\_rqst}}{../ns-2/srm.cc}{SRMAgent::recv\_rqst}
will check whether it needs to schedule requests for other missing data.
If it has received this request
before it was aware that the source had generated this data message
(\ie, the sequence number of the request is higher than 
the last known sequence number of data from this source),
then the agent can infer that it is missing this, as well as data
from the last known sequence number onwards;
it schedules requests for all of the missing data and returns.
On the other hand, if the sequence number of the request is less
than the last known sequence number from the source,
then the agent can be in one of three states:
(1) it does not have this data, and has a request pending for it,
(2) it has the data, and has seen an earlier request,
    upon which it has a repair pending for it, or
(3) it has the data, and it should instantiate a repair.
All of these error recovery mechanisms are done in OTcl;
\fcn[]{recv\_rqst} invokes the instance procedure
\fcnref{\proc[sender, msgid,
  requester]{recv-rqst}}{../ns-2/srm.tcl}{Agent/SRM::recv-rqst}
for further processing.

\paragraph{Repair Packets}
On receiving a repair, 
\fcnref{\fcn[sender, msgid]{recv\_repr}}{../ns-2/srm.cc}{SRMAgent::recv\_repr}
will check whether it needs to schedule requests for other missing data.
If it has received this repair
before it was aware that the source had generated this data message
(\ie, the sequence number of the repair is higher than 
the last known sequence number of data from this source),
then the agent can infer that it is missing all
data between the last known sequence number and that on the repair;
it schedules requests for all of this data,
 marks this message as received, and returns.
On the other hand, if the sequence number of the request is less
than the last known sequence number from the source,
then the agent can be in one of three states:
(1) it does not have this data, and has a request pending for it,
(2) it has the data, and has seen an earlier request,
    upon which it has a repair pending for it, or
(3) it has the data, and probably scheduled a repair for it at some time;
    after error recovery, its hold down timer (equal to three times its
    distance to some requester) expired, at which time the pending object
    was cleared.  In this last situation, the agent will simply ignore
    the repair, for lack of being able to do anything meaningful.
All of these error recovery mechanisms are done in OTcl;
\fcn[]{recv\_repr} invokes the instance procedure
\fcnref{\proc[sender, msgid]{recv-repr}}{%
  ../ns-2/srm.tcl}{Agent/SRM::recv-rqst}
to complete the loss recovery phase for the particular message.
  
\paragraph{Session Packets}
On receiving a session message,
the agent updates its sequence numbers for all active sources,
and computes its instantaneous distance to the sending agent if possible.
The agent will ignore earlier session messages from a group member,
if it has received a later one out of order.
  
Session message processing is done in
\fcnref{\fcn[]{recv\_sess}}{../ns-2/srm.cc}{SRMAgent::recv\_sess}.
The format of the session message is:
\tup{count of tuples in this message, list of tuples},
where each tuple indicates the
\tup{sender id, last sequence number from the source, time the last
  session message was received from this sender, time that that message
  was sent}.
The first tuple is the information about the local agent%
\footnote{Note that this implementation of session message handling
  is subtly different from that used in \emph{wb} or described in
  \cite{Floy95:Reliable}.
  In principle, an agent disseminates a list of the data it has
  actually received.
  Our implementation, on the other hand, only disseminates
  a count of the last message sequence number per source that the
  agent knows that that the source has sent.
  This is a constraint when studying aspects of loss recovery
  during partition and healing.
  It is reasonable to expect that the maintainer of this code will fix
  this problem during one of his numerous intervals of copious spare time.}.

\section{Loss Detection---The Class SRMinfo}
\label{sec:srminfo}

A very small encapsulating class, entirely in C++,
tracks a number of assorted state information.
Each member of the group, $n_i$,  uses one SRMinfo block for every other
member of the group.

An SRMinfo object about group member $n_j$ at $n_i$,
contains information about the session messages
received by $n_i$ from $n_j$.
$n_i$ can use this information to compute its distance to $n_j$.

If $n_j$ sends is active in sending data traffic, then
the SRMinfo object will also contain information about the
received data, including a bit vector indicating all packets
received from $n_j$.

The agent keeps a list of SRMinfo objects, one per group member,
in its member variable, \code{sip_}.
Its method, \fcn[int sender]{get\_state}
will return the object corresponding to that sender,