Comp 388/488 - advanced TCP/IP  Dordal  April 17, 2002
program 3                 due: May 7, Tuesday (or within 1-2 days) 

You are to use ns to make some measurements of the average queue length
under tcp. The conjecture is that for a single active TCP Reno
connection, the average window size used is about half 
of the *path's* actual capacity, which is the sum of
   * queue capacity at the bottleneck link
   * in-transit capacity (no-load-RTT * bottleneck_bandwidth)
That is, the congestion window size varies uniformly from 0 to full. 
You are to collect evidence for or against this hypothesis.

Note that if there is very little in-transit capacity, this hypothesis
states that the average queue length should be 75% of the maximum;
the window size will range between 50% and 100% of maximum, and 
most of that window will sit in the queue.
However, if the in-transit capacity matches the queue capacity, 
then as the total capacity oscillates between 50% and 100% of
maximum, the *queue* capacity will oscillate between 0% and 100%, etc.

To do this you will have to create trace files for specific links, and
then analyze the files for queue size changes.  You should also accumulate
statistics for how long (if ever) the queue is empty.

To create a tracefile, "link.tr", between nodes x and y, put the
following into your ns tcl script:
    set tr [open link.tr w]             # create the file for writing
    $ns trace-queue $x $y $tr
Note that "tr" is the name of the file variable within the program; the
file's "external" name is "link.tr"; this is the file that will
exist after the program has run.

Note also that the queue is considered by ns to be attached to a _link_,
from x to y above, and not to the node x. Note also that the queue
is considered by ns to be attached to a _link_, from x to y above,
and not to the node x.  

A trace file consists of lines with 12 fields:

1. disposition (+: arrival, -: departure, d: drop, r: received at far end)
2. time
3. link src (always the same if you only trace between two fixed nodes
   as above; equal to node x in the example above)
4. link dest (node y above)
5. type, eg "tcp"
6. packet size
7. flag string, which we'll ignore
8. flowid, useful for distinguishing between multiple connections
9. srchost.srcport
10. dsthost.dstport
11. sequence number
12. unique packet id

We'll only be concerned with a few of these.

The first field tells you what was done with the packet. If a packet
arrived ("+"), you increment the queue size. If a packet departed ("-"),
you decrement (and verify, if desired, that the queue size did not
become negative). If the packet was dropped ("d"), you decrement the
queue size (and verify, if desired, that the queue was full). For "r"
events, this means that the packet was received at the other end of the
link; you simply ignore these.

In addition, a tracefile can contain lines indicating when certain
variables change. Here is the ns tcl code to trace cwnd_ and ssthresh_:
	$tcp0 attach $f
	$tcp0 tracevar cwnd_
	$tcp0 tracevar ssthresh_
If you're analyzing a tracefile, you have to discard lines of this 
"variable-trace" format.

What you need to do is maintain a running average of the queue size, by
(a) keeping track of the size, and (b) for each time interval [t1,t2]
over which the queue has a given size s, add s*(t2-t1) to a running
total. When you're done, divide the running total by the total
simulation time to get the average.

Here is a simple script in the "awk" language, available on abel, that
does this. Awk parses the input lines into fields, denoted $1 through
$12 (though we only use $1 and $2 here). Awk is string-based; you can get 
further information from the "man" page, obtained on abel by typing "man awk",
or else by searching on the web.




   BEGIN  {size=0; prevtime=0.0;sum=0.0;}			# initialization
   /cwnd_/      {next}					# skip these lines
   /ssthresh_/  {next}					# skip these lines
   /ack_/       {next}					# skip these lines
   /maxseq_/    {next}					# skip these lines
   $1 == "r"    {next}					# skip these lines
         { sum += size*($2-prevtime); prevtime=$2; }	# do for all other lines
   $1 == "+" {size+=1}
   $1 == "-" {size-=1} # ; if (size==0) print "size zero at ", $2}
   $1 == "d" {size-=1}
   END {print " final time is ", prevtime, " avg queue is ", sum/prevtime}

Put this into a file, say "queue_avg", and then run it via
        awk -f queue_avg link.tr

Be sure you set the window_ variable large enough so that it is always
larger than cwnd_, with
	Agent/TCP set window_ 100

Here are some questions to answer:
1. For a single tcp connection with a bottleneck link, find out the
average queue size and how much time the queue is empty.
Do this for several different combinations of queue size and 
path capacity, and in particular for different values of queue size
and path capacity but with the same ratio. How strongly does average
queue size correlate with this ratio?

One approach would be to make several trials with the same qsize/RTT ratio
(for a given bottleneck link, no-load-RTT is proportional to transit capacity).
Another might be to graph the ratio qsize/RTT for one fixed queue-limit,
as one graph series, and to graph the same ratio as a second series for
a second fixed queue-limit, and see how well the graphs coincide.
Either way, you should explain your procedure.

2. Create a scenario in which two TCP Reno connections share the
bandwidth reasonably fairly. Then change one to TCP Vegas, and see what
the relative bandwidth and queue utilization are.

Note that when working with more than one connection you'll have to use
the flowid field ($8) to keep separate totals for each flow.