[ns] Re: How can I calculate the packet loss of one flow(session) on the run time

[Brian Lee Bowers <bowersb@lanl.gov>]

On Thursday 21 June 2001 10:22, Huan Pham wrote:
> Thanks Brian for the reply, but here come the question again.
>
> I am simulating this topology, where servers 2-5 are sending
> packets to clients 6-20
>
>
>             6        2  3
>           \ |        | /
>          -- 0 -------1 --4
>           / |         \
>            20         5

From the looks of things, 0 <---> 1 is a bottleneck.  If packets are 
dropped, they will either be dropped from the queue at 0 or the queue 
at 1.  (Go with me for the moment, there is a more general solution 
lurking here somewhere, I just have to talk it through).

If you have the disk space to store the traceall file, you know all 
of the packets that are dropped, you know which link they were 
dropped from, you know the source and the destination, you know the 
sequence number, and you know the unique packet ID.  All of this 
information comes from the traceall file.

Let me assume that I want to know the number of packets originating 
at node 4 that are eventually dropped.  I don't care where they are 
dropped, only that they are dropped.

The line below is an actual drop from my most recent out.tr.  What 
does it tell me?

d 1.409284 4 5 tcp 1000 ------- 1 0.0 2.0 122 436

The packet was dropped at 1.409284 seconds into the sim.  The packet 
size is 1000 bytes.  The packets was dropped on the link from node 4 
to node 5.  The packet originated at node 0 and was destined for node 
2.

Using Perl, I can use a regular expression like the following to find 
all dropped packets.

/^d/

The only lines of the out.tr file that have d as the first character 
are for packets that were dropped (in fact, the only time a lower 
case d should ever appear is for a drop packet, but... :)

First cut, I don't really care about the retransmits, I want to know 
about lost packets.  I can get a count simply by looping through the 
whole out.tr file one line at a time, looking for dropped packets.

if (/^d/) {
  $drops++;
}

OK, now I want to be more specific, I want to find packets that were 
dropped from the bottleneck link, originating from a specific host.

I copied the drop line from above, simply to get the regular 
expression right.  I'm going to use my bottleneck link (4 to 5) 
rather than yours (0 to 1).

d 1.409284 4 5 tcp 1000 ------- 1 0.0 2.0 122 436

if 
(/^d\s\d*\.\d*\s4\s5\s...\s\d*\s.......\s\d*\s(\d*)\.\d*\s(\d*)\.\d*/)

An ugly regular expression.  But now I can do some further checks 
because Perl is so helpful.  I know on which link the drop occurred - 
4 to 5 or the regular expression wouldn't have matched.  I used 
parentheses to keep track of my origination and my destination nodes, 
so that I can count only drops of interest.  Assume that I 
initialized variable $source with the node number of the source I'm 
worried about:

  if ($1 == $source)
    $drops++;

You need not be so specific.  If you want to keep an array of source 
nodes whose packets were dropped on the bottleneck link, Perl will 
help you here too.  Get rid of the above "if" statement and replace 
it with

  $drops[$1]++;

Then after you've parsed the whole file, you can print the results 
quickly.

There is no need to read the whole file into memory at once.  I'm 
processing one line at a time to find drops, so I need one line from 
the trace file at a time.  If you have a large number of nodes, you 
might get a moderately sized array - 32KB for 8K nodes - but it 
should not be an unreasonable size.

If you want to compare the number of packets successfully transmitted 
across the bottleneck link, compared to the number of packets dropped 
trying to get into the queue, a second regular expression can be used 
(a second, SIMPLER regular expression).

> > Several methods come to mind for determining number of packets
> > lost for a flow:
> >
> > 1)  parse the trace file.  This is fairly simple with Perl.
> > Depending on how much of the information you need, the regular
> > expressions can get a little nasty looking, but they aren't
> > difficult.
>
> If I use TraceAll file, then the file size get as big as 1Gbyte.
> Currently I read all the data to an array and process it, and RAM
> size is a problem, not the Harddisk size.  I can not think of any
> other better algorithm that does not read all the data to an array
> and process it. For example, if it just reads a short chunk of
> data, processes them and read another.  The algorithm must be very
> complicated.

What are you trying to do that you need all of the data in memory at 
once?  Tools such as Perl can allow you to discard the portions you 
don't care about.  In a previous life, I had to use SAS to perform 
various analyses of highway traffic crash data.  I learned quickly 
not to try to process entire data sets in memory all at once.  
Discard the pieces that don't provide any benefit to your analysis.  

-- 
Brian Lee Bowers	|	RADIANT Team
bowersb@lanl.gov	|	Los Alamos National Laboratory