srm.tex

柯老师网站上找到的

\def\c#1{\ensuremath{C_{#1}}}
\def\d#1{\ensuremath{D_{#1}}}

\chapter{Agent/SRM}
\label{chap:agent/srm}

This chapter describes the internals of the SRM implementation in \ns.
The chapter is in three parts:
the first part is an overview of a minimal SRM configuration,
and a ``complete'' description of the configuration parameters 
of the base SRM agent.
The second part describes the architecture, internals, and the code path
of the base SRM agent.
The last part of the chapter is a description of the extensions
for other types of SRM agents that have been attempted to date.

The procedures and functions described in this chapter can be found in
\nsf{tcl/mcast/srm.tcl}, \nsf{tcl/mcast/srm-adaptive.tcl},
\nsf{tcl/mcast/srm-nam.tcl}, \nsf{tcl/mcast/srm-debug.tcl}, and
\nsf{srm.\{cc, h\}}.

\section{Configuration}
\label{sec:srm-config}

Running an SRM simulation requires
creating and configuring the agent,
attaching an application-level data source (a traffic generator), and
starting the agent and the traffic generator.

\subsection{Trivial Configuration}

\paragraph{Creating the Agent}
\begin{program}
        set ns [new Simulator]          \; preamble initialization;
        $ns enableMcast
        set node [$ns node]                \; agent to reside on this node;
        set group [$ns allocaddr]           \; multicast group for this agent;

        {\bfseries{}set srm [new Agent/SRM]}
        $srm  set dst_ $group            \; configure the SRM agent;
        {\bfseries{}$ns attach-agent $node $srm}

        $srm set fid_ 1                \; optional configuration;
        $srm log [open srmStats.tr w]   \; log statistics in this file;
        $srm trace [open srmEvents.tr w]  \; trace events for this agent;
\end{program}
The key steps in configuring a virgin SRM agent are to assign
its multicast group, and attach it to a node.

Other useful configuration parameters are
to assign a separate flow id to traffic originating from this agent,
to open a log file for statistics, and
a trace file for trace data%
\footnote{%
Note that the trace data can also be used
to gather certain kinds of trace data.
We will illustrate this later.}.

The file
\fcnref{\code{tcl/mcast/srm-nam.tcl}}{../ns-2/srm-nam.tcl}{Agent/SRM::send}
contains definitions that overload the agent's \code{send} methods;
this separates control traffic originating from the agent by type.
Each type is allocated a separate flowID.
The traffic is separated into session messages (flowid = 40),
requests (flowid = 41), and repair messages (flowid = 42).
The base flowid can be changed by setting global variable \code{ctrlFid}
to one less than the desired flowid before sourcing \code{srm-nam.tcl}.
To do this, the simulation script must source \code{srm-nam.tcl}
before creating any SRM agents.
This is useful for analysis of traffic traces, or
for visualization in nam.

\paragraph{Application Data Handling}
The agent does not generate any application data on its own;
instead, the simulation user can connect any traffic generation
module to any SRM agent to generate data.
The following code demonstrates
how a traffic generation agent can be attached to an SRM agent:
\begin{program}
        set packetSize 210
        set exp0 [new Application/Traffic/Exponential]    \; configure traffic generator;
        $exp0 set packetSize_ $packetSize
        $exp0 set burst_time_ 500ms 
        $exp0 set idle_time_ 500ms
        $exp0 set rate_ 100k 

        {\bfseries{}$exp0 attach-agent $srm0} \; attach application to SRM agent;
        {\bfseries{}$srm0 set packetSize_ $packetSize} \; to generate repair packets of appropriate size;
        $srm0 set tg_ $exp0 \; pointer to traffic generator object;
        $srm0 set app_fid_ 0 \; fid value for packets generated by traffic generator;
\end{program}
The user can attach any traffic generator to an SRM agent.
The SRM agent will add the SRM headers, 
set the destination address to the multicast group, and
deliver the packet to its target.
The SRM header contains the type of the message,
the identity of the sender,
the sequence number of the message,
and (for control messages), the round for which this message is being sent.
Each data unit in SRM is identified as
\tup{sender's id, message sequence number}.

The SRM agent does not generate its own data;
it does not also keep track of the data sent,
except to record the sequence numbers of messages received
in the event that it has to do error recovery.
Since the agent has no actual record of past data,
it needs to know what packet size to use for each repair message.
Hence, the instance variable \code{packetSize_} specifies the size
of repair messages generated by the agent.

\paragraph{Starting the Agent and Traffic Generator}
The agent and the traffic generator must be started separately.
\begin{program}
        {\bfseries{}\fcnref{$srm start}{../ns-2/srm.tcl}{Agent/SRM::start}}
        {\bfseries{}\fcnref{$exp0 start}{../ns-2/srm.tcl}{Agent/SRM::start-source}}
\end{program}
Alternatively, the traffic generator can be started from the SRM Agent:
\begin{program}
        {\bfseries{}\fcnref{$srm0 start-source}{../ns-2/srm.tcl}{Agent/SRM::start-source}}
\end{program}
At \code{start}, the agent joins the multicast group, and 
starts generating session messages.
The \code{start-source} triggers the traffic generator to start sending
data.

\subsection{Other Configuration Parameters}
\label{sec:config-param}

In addition to the above parameters,
the SRM agent supports additional configuration variables.
Each of the variables described in this section is
both an OTcl class variable and an OTcl object's instance variable.
Changing the class variable changes the default value
for all agents that are created subsequently.
Changing the instance variable of a particular agent
only affects the values used by that agent.
For example,
\begin{program}
                Agent/SRM set D1_ 2.0 \; Changes the class variable;
                $srm set D1_ 2.0        \; Changes D1_ for the particular $srm object only;
\end{program}

The default request and repair timer parameters \cite{Floy95:Reliable}
for each SRM agent are:
\begin{program}
        Agent/SRM set C1_       2.0 \; request parameters;
        Agent/SRM set C2_       2.0
        Agent/SRM set D1_       1.0 \; repair parameters;
        Agent/SRM set D2_       1.0
\end{program}
It is thus possible to trivially obtain two flavors of SRM agents
based on whether the agents use probabilistic or deterministic
suppression by using the following definitions:
\begin{program}
        Class Agent/SRM/Deterministic -superclass Agent/SRM
        Agent/SRM/Deterministic set C2_ 0.0
        Agent/SRM/Deterministic set D2_ 0.0

        Class Agent/SRM/Probabilistic -superclass Agent/SRM
        Agent/SRM/Probabilistic set C1_ 0.0
        Agent/SRM/Probabilistic set D1_ 0.0
\end{program}
In \href{a later section}{Section}{sec:extensions},
we will discuss other ways of extending the SRM agent.

Timer related functions are handled by separate objects
belonging to the class  SRM.
Timers are required for loss recovery and sending periodic session messages.
There are loss recovery objects to send request and repair messages.
The agent creates a separate request or repair object to handle each loss.
In contrast, the agent only creates one session object to send
periodic session messages.
The default classes the express each of these functions are:
\begin{program}
        Agent/SRM set requestFunction_  "SRM/request"
        Agent/SRM set repairFunction_   "SRM/repair"
        Agent/SRM set sessionFunction_  "SRM/session"

        Agent/SRM set requestBackoffLimit_      5       \; parameter to requestFunction_;
        Agent/SRM set sessionDelay_             1.0     \; parameter to sessionFunction_;
\end{program}
The instance procedures
\fcnref{\proc[]{requestFunction}}{../ns-/srm.tcl}{Agent/SRM::requestFunction},
\fcnref{\proc[]{repairFunction}}{../ns-/srm.tcl}{Agent/SRM::repairFunction},
and
\fcnref{\proc[]{sessionFunction}}{../ns-/srm.tcl}{Agent/SRM::sessionFunction}
can be used to change the default function for individual agents.
The last two lines are specific parameters used by the request 
and session objects.
The \href{following section}{Section}{sec:architecture}
describes the implementation of theses objects in greater detail.

\subsection{Statistics}
Each agent tracks two sets of statistics:
statistics to measure the response to data loss,
and overall statistics for each request/repair.
In addition, there are methods to access other
information from the agent.

\paragraph{Data Loss}
The statistics to measure the response to data losses
tracks the duplicate requests (and repairs),
and the average request (and repair) delay.
The algorithm used is documented in Floyd \etal \cite{Floy95:Reliable}.
In this algorithm,
each new request (or repair) starts a new request (or repair) period.
During the request (or repair) period, the agent measures
the number of first round duplicate requests (or repairs)
until the round terminates either due to receiving a request (or
repair), or due to the agent sending one.
% These statistics are used by the adaptive timer algorithms;
% we will describe our implementation of these algorithms
% in the following subsections.
The following code illustrates how the user can simple retrieve the
current values in an agent:
\begin{program}
                set statsList [$srm array get statistics_]
                array set statsArray [$srm array get statistics_]
\end{program}
The first form returns a list of key-value pairs.
The second form loads the list into the \code{statsArray} for further manipulation.
The keys of the array are
\code{dup-req}, \code{ave-dup-req}, \code{req-delay}, \code{ave-req-delay},
\code{dup-rep}, \code{ave-dup-rep}, \code{rep-delay}, and \code{ave-rep-delay}.

\paragraph{Overall Statistics}
In addition, each loss recovery and session object keeps track of
times and statistics.
In particular, each object records its
\code{startTime}, \code{serviceTime}, \code{distance}, as are relevant to that object;
startTime is the time that this object was created,
serviceTime is the time for this object to complete its task, and the
distance is the one-way time to reach the remote peer.

For request objects, startTime is the time a packet loss is detected,
serviceTime is the time to finally receive that packet,
and distance is the distance to the original sender of the packet.
For repair objects, startTime is the time that a request for
retransmission is received, serviceTime is the time send a repair,
and the distance is the distance to the original requester.
For both types of objects, the serviceTime is normalized by the
distance.
For  the session object,
startTime is the time that the agent joins the multicast group.
serviceTime and distance are not relevant.

Each object also maintains statistics particular to that type of object.
Request objects track the number of duplicate requests and repairs received,
the number of requests sent, and the number of times this object
had to backoff before finally receiving the data.
Repair objects track the number of duplicate requests and repairs,
as well as whether or not this object for this agent sent the repair.
Session objects simply record the number of session messages sent.

The values of the timers and the statistics for each object are written
to the log file every time an object completes the error recovery function
it was tasked to do.
The format of this trace file is:
\begin{program}
                \tup{prefix} \tup{id} \tup{times} \tup{stats}
{\itshape{}where}
\tup{prefix} is         \tup{time} n \tup{node id} m \tup{msg id} r \tup{round}
                \tup{msg id} is expressed as \tup{source id:sequence number}
\tup{id} is             type \tup{of object}
\tup{times} is          list of key-value pairs of startTime, serviceTime, distance
\tup{stats} is          list of key-value pairs of per object statistics
                \code{dupRQST}, \code{dupREPR}, \code{#sent}, \code{backoff}             {\itshape for request objects}
                \code{dupRQST}, \code{dupREPR}, \code{#sent}                      {\itshape for repair objects}
                \code{#sent}                                        {\itshape for session objects}
\end{program}
The following sample output illustrates the output file format (the lines
have been folded to fit on the page):
{\small
\begin{verbatim}
 3.6274 n 0 m <1:1> r 1 type repair serviceTime 0.500222 \
        startTime 3.5853553333333332 distance 0.0105 #sent 1 dupREPR 0 dupRQST 0
 3.6417 n 1 m <1:1> r 2 type request serviceTime 2.66406 \
        startTime 3.5542666666666665 distance 0.0105 backoff 1 #sent 1 dupREPR 0 dupRQST 0
 3.6876 n 2 m <1:1> r 2 type request serviceTime 1.33406 \
        startTime 3.5685333333333333 distance 0.021 backoff 1 #sent 0 dupREPR 0 dupRQST 0
 3.7349 n 3 m <1:1> r 2 type request serviceTime 0.876812 \
        startTime 3.5828000000000002 distance 0.032 backoff 1 #sent 0 dupREPR 0 dupRQST 0
 3.7793 n 5 m <1:1> r 2 type request serviceTime 0.669063 \
        startTime 3.5970666666666671 distance 0.042 backoff 1 #sent 0 dupREPR 0 dupRQST 0
 3.7808 n 4 m <1:1> r 2 type request serviceTime 0.661192 \
        startTime 3.5970666666666671 distance 0.0425 backoff 1 #sent 0 dupREPR 0 dupRQST 0
\end{verbatim}
}

\paragraph{Miscellaneous Information}
Finally, the user can use the following methods to gather
additional information about the agent:
\begin{list}{\textbullet}{}
\item
  \fcnref{\proc[]{groupSize?}}{../ns-2/srm.tcl.html}{Agent/SRM::groupSize?}