NS by Example 笔记（17）SRM Example

SRM using NS-2

 

 

这一节给出一个关于在NS中实现SRM的概况。运行一个SRM模拟需要

• 建立并配置代理creating and configuring the agent
• 添加一个应用层的数据源application level data source (a traffic generator)
• 启动代理和流量产生器starting the agent and the traffic generator

 

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 log file for statistics, and a trace file for trace data. 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 user can attach any traffic generator to n 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. SRM header contains the type of message, identity of the sender, the sequence number of the message, the round for which this message is being sent.Each data unit in SRM is identified as < 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 the past data, it needs to know what packet size to use for each repair message. The agent and the traffic generator must be started separately using : $srm start and $exp0 start

 

At start, the agent joins the multicast group and starts generating the session messages.

 

Each agent tracks two sets of statistics: statistics to measure the response to data loss and overall statistics for each request/repair.

Data Loss:

 

The statistics to measure the response to data losses track the duplicate request (and repair), and the average request (and repair) delay. 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 repair) until the round terminates either due to receiving a request (or repair) or due to the agent sending one.

 

 

Overall Statistics:

 

In addition, each loss recovery and session object keeps a track of times and statistics. In particular, each object records its startTime. ServiceTime, distance, are relevant to the 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 the 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 to send a repair and the distance is the distance to the original requester. For both types of objects, the serviceTime is normalized by 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 that 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 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.

 

 

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:

 

                                       <prefix> <tag> <type of entry> <values>

 

The prefix is as described in the previous section for statistics. The tag is Q for requets objects, P for repair objects, and S for session objects.

 

 

Architecture and Internals:

 

The SRM agent implementation splits the protocol functions into packet handling, loss recovery, and session message activity. 

• Packet handling consists of forwarding application data messages, sending and receipt of control messages. These activities are executed by C++ methods.

    

• Error detection done in C++ due to receipt of error messages. However, loss recovery is entirely done through instance procedures in Otcl.

   

• 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

   

 

Packet Handling: Processing received messages.

 

The recv() method can receive 4 types of messages: data, request, repair and session messages.

 

Data Packets

 

The agent does not generate any data messages. The user has to specify an external agent to generate traffic. The recv() method must distinguish between locally originated data, that must be sent to the multicast group, and the data received from the 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, the recv_data(sender, msgid) will update its state marking message <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, recv-data {sender,msgid}.

 

Currently, there is no provision for 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 instance variable packetSize_. However, the agent assumes that any application data is placed in the data portion of the packet, pointed to by

 

packet->accessdata().

Request Packets :

 

On receiving a request, recv_rqst(sender, msgid) 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(i.e the sequence no. of this message is higher than the last known sequence no. of data from this source), then the agent can infer that it is missing this, as well as data from the last known sequence no. onwards; it schedules requests for all of the missing data and returns. On the other hand, if the seuqence no. of the request is less than the last know sequence no. from the source, then the agent can be in one of the three states: a) it does not have this data, and has a requets pending for it, b) it has the data, and has seen an earlier request, upon which it has a repair pending for it, or c) it has the data, and it should instantiate a repair. All of these error recovery mechanisms are done in OTcl; recv_rqst() invokes the instance procedure recv-rqst{sender, msgid, requester} for futher processing.

Repair Packets :

 

On receiving a repair packet, recv_repr(sender, msgid) 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(i.e. the sequence no. of the repair is higher than the last known sequence no. from this source), then the agent can infer that it is missing all data between the last known sequence no. 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 no. of the request is lesser than the last known sequence no. from the source, then the agent can be in one of the 3 states; a) it does not have the data. and has a request pending for it, b) it has the data, and has seen an earlier request, upon which it has a repair pending for it, or c) it has the data, and probably scheduled a repair for it at some time; after recovery it holds down its 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; recv_repr() invokes the instance procedure recv-repr{sender, msgid} to complete the loss recovery phase for the particular message. 

 

 

Session Packets :

 

On receiving a session message, the agent updates its sequence numbers for all the active sources, and computes its instantaneous distance to the sending agent if possible. This 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 recv_sess(). The format of the session message is:<count of tuples in this message, list of tuples>, where each tuple indicates the <sender id, last sequence no. from the source, time the last session message was received from this sender, time that the message was sent>. The first tuple is the information about the local agent.

 

It is possible to trivially obtain two flavors of SRM based on whether the agents use probabilistic or deterministic suppression. The default request and repair timer parameter for each SRM agent are

            Agent/ SRM set C1_ 2.0

            Agent/ SRM set C2_ 2.0

            Agent/ SRM set D!_ 1.0

            Agent/ SRM set D2_ 1.0

Deterministic Suppressions:

 

Class Agent/ SRM/ Deterministic – superclass Agent / SRM

Agent/SRM/ deterministic sets C2_ 0.0

Agent /SRM/ deterministic sets D2_ 0.0

 

Probabilistic Suppressions:

 

Class Agent/ SRM/ Probabilistic – superclass Agent / SRM

Agent/SRM/ Probabilistic sets C1_ 0.0

Agent /SRM Probabilistic sets D1_ 0.0

Loss Detection:

 

The SRM agent implementation splits the protocol functions into  

• Packet handling,
• Loss recovery, and
• Session message activity.

 

Packet handling consists of forwarding application data messages, sending and receipt of control messages. These applications are executed by C++ methods.

 

Error detection is done in C++ due to receipt of messages. However, the loss recovery is entirely done through instance procedures in OTcl.

 

Sending and processing of messages is accomplished through C++; the policy about when these messages should be sent is decided by instance procedures in OTcl.

 

A very small encapsulating class, entirely in C++, tracks a number of assorted state information. Each member of a group, ni, uses one SRMinfo block for every other member of the group. An SRMinfo object about group member nj at ni, contains information about session messages received by ni from nj. Ni can use this information to compute its distance to nj. If nj, 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 nj.

 

The agent keeps a list of SRMinfo objects, one per group member, in its member variable, sip_. Its method get_state(int sender) will return the object corresponding to that sender, possibly creating that object, if it did not already exist. The class SRMinfo has two methods to access and set the bit vector, i.e.

 

IfReceived(int id) indicates whether the particular message from the appropriate sender, with id id was received at ni.

 

SetReceived(int id) to set the bit to indicate that the particlar message from the appropriate sender, with id id was received at ni.

 

The session message variables to access timing information are public; no encapsulating methods are provided. These are:

 

Int lsess_; /* # of last session msg. Received */
Int sendTime_; /* Time session msg. # sent */
Int recvTime_; /* Time session message # received */
Double distance_; /* Delay between nodes */
int ldata_; /* Data Messages */

 

Loss Recovery Objects:

Timers are used to control when any particular control message is to be sent. The SRM agent uses a separate class SRM to do the timer based processing. 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 class SRM/request; agents that receive a request and have the required data will instantiate an object in the class SRM/ repair.

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 by instance procedures of the corresponding object in OTcl.

 

 

Repair Mechanisms:

 

 

The agent will initiate a repair if it receives a request for a packet, and it does not have a request object pending_ for that packet. The default repair object belongs to the class SRM/repair. Barring minor differences, the sequence of events and the instance procedures in this class are identical to those for SRM/request.

   

•  

   

  Sample Code :

  # STAR TOPOLOGY
  
  source /usr/lib/ns-allinone-2.1b4/ns-2/tcl/mcast/srm-nam.tcl ;# to separate $
  source /usr/lib/ns-allinone-2.1b4/ns-2/tcl/mcast/srm-debug.tcl ;# to trace del$
  Simulator set NumberInterfaces_ 1
  set ns [new Simulator]
  Simulator set EnableMcast_ 1
  $ns trace-all [open out.tr w]
  $ns namtrace-all [open out.nam w]
  set srmSimType Probabilistic
  $ns color 0 red ;#data source
  $ns color 40 blue ;#session
  $ns color 41 green ;#request
  $ns color 42 white ;#repair
  $ns color 4 red ;#source node
  
  # Creating The Nodes
  set nmax 8
  for {set i 0} {$i <= $nmax} {incr i} {
        set n($i) [$ns node]
  }
  $n(1) color "red"
  
  # Creating The Links
  for {set i 1} {$i <= $nmax} {incr i} {
        $ns duplex-link $n($i) $n(0) 1.5Mb 10ms DropTail
  }
  
  # Orienting The Links
  $ns duplex-link-op $n(0) $n(1) orient right
  $ns duplex-link-op $n(0) $n(2) orient right-up
  $ns duplex-link-op $n(0) $n(3) orient up
  $ns duplex-link-op $n(0) $n(4) orient left-up
  $ns duplex-link-op $n(0) $n(5) orient left
  $ns duplex-link-op $n(0) $n(6) orient left-down
  $ns duplex-link-op $n(0) $n(7) orient down
  $ns duplex-link-op $n(0) $n(8) orient right-down
  set group 0x8000
  set cmc [$ns mrtproto CtrMcast {}]
  $ns at 0.3 "$cmc switch-treetype $group"
  
  # SRM TRACE EVENTS
  set srmStats [open srmStats.tr w]
  set srmEvents [open srmEvents.tr w]
  set fid 0
  for {set i 1} {$i <= $nmax} {incr i} {
        set srm($i) [new Agent/SRM/$srmSimType]
        $srm($i) set dst_ $group
        $srm($i) set fid_ [incr fid]
        $srm($i) log $srmStats
        $srm($i) trace $srmEvents
        $ns at 0.5 "$srm($i) start"
        $ns attach-agent $n($i) $srm($i)
  }
  
  # Attach a CBR Agent to srm(1)
  set packetSize 800
  set s [new Application/Traffic/CBR]
  $s set packet_size_ $packetSize
  $s set interval_ 0.02
  $s attach-agent $srm(1)
  $srm(1) set tg_ $s
  $srm(1) set app_fid_ 0
  $srm(1) set packetSize_ $packetSize
  $ns at 2.0 "$srm(1) start-source"
  set loss_module [new SRMErrorModel]
  $loss_module drop-packet 2 10 1
  $loss_module drop-target [$ns set nullAgent_]
  $ns at 0.75 "$ns lossmodel $loss_module $n(1) $n(0)"
  $ns at 4.0 "finish $s" proc distDump interval {
        global ns srm
        foreach i [array names srm] {
              set dist [$srm($i) distances?]
              if {$dist != ""} {
                    puts "[format %7.4f [$ns now]] distances $dist"
              }
        }
        $ns at [expr [$ns now] + $interval] "distDump $interval"
  }
  proc finish src {
        global prog ns env srmStats srmEvents srm nmax
        $src stop
        $ns flush-trace
        close $srmStats
        close $srmEvents
        puts "converting output to nam format..."
        if [info exists env(DISPLAY)] {
              puts "running nam..."
              exec nam out.nam &
        } else {
              exec cat srmStats.tr >@stdout
        }
        exit 0 
  }
  $ns run