Modification of RED AQM in NS2

Please read the previous post here first to get some background information about RED.

0. Download ns2, Compile it and Install it.

This is a preparation step. It’s not the focus of this post, please refer to reference 1 for details. Note that since we’re going to modify NS2, we’ll need to download and source code and build it ourselves.  

1. Change red.cc and red.h

RED calculates the probability of dropping a packet by 2 steps when average queue size falls in between th_min and th_max. The first step is to calculate a probability called Pb, which is based on the formula below,

Pb = Pmax*(avg – th_min)/(th_max-th_min)                                        (1)

It can be seen that the probability Pb is calculated based on a linear function.

In the second step, RED counts the number of packets have gone through the gateway (count) since last packet is dropped from the flow and apply the following formula,

Pa = Pb / (1 – count*Pb)                                                                             (2)

In this part, we modified the first step by applying 4 different functions to calculate Pb and compare the results. The curves for the 4 functions are roughly as below,

image

Figure 1. Five Different Functions to Evaluate Pb

1.1 Analysis

You can ignore this part and jump to 1.2 if you only want to know how to change a protocol in NS2.

NS2 RED queue implementation doesn’t use the formula (1) above directly, instead it uses the formula below,

Pb = Pmax*(v_a * v_ave + v_b)                                                       (3)

where v_a = 1.0 / (th_max – th_min), v_ave is the average queue size, and v_b = -th_min / (th_max – th_min). This forumla is equivalent to formula (1).

For concave function v1, we use log function,

Pb = Pmax*(m*log(v_ave) + n)                                                        (4)

As the curve intersects with original linear function at th_min and th_max, we have the following,

0 = Pmax*(m*log(th_min) + n)                                                         (5)

Pmax = Pmax*(m*log(th_max + n))                                                 (6)

Also the original linear function gives us the function,

0 = Pmax*(v_a*th_min + v_b)                                                          (7)

with (5) (6) and (7), we can get values for m and n in formula (4),

m = 1/(log(th_max) – log(-v_b/v_a))                                                (8)

n = -m*log(-v_b/v_a)                                                                          (9)

Similarly, we can express the formula for function v4 the convex function (we chose exponential function) using th_max, v_b and v_a as below,

Pb = Pmax*(m*exp(v_ave)+n)                                                          (10)

where,

m = 1/(exp(th_max) – exp(-v_b/v_a))                                             (11)

n = -m*exp(-v_b/v_a)                                                                       (12)

As for function v2 and v3, which are piecewise linear functions, we express the functions as below,

Pb = Pmax*(m*v_ave + p) when v_ave in [th_min, (th_min+th_max)/2] (13)

Pb = Pmax*(n*ave + q) when v_ave in [(th_min+th_max)/2, th_max]

We can get the following equations,

m*th_min + p = 0                                                                                  (14)

m*[(th_min+th_max)/2] + p = n*[(th_min+th_max)/2] + q         (15)

n*th_max + q = 1                                                                                  (16)

With (14), (15) and (16), we can derive the relationship between m and n,

n = [m*(th_max+th_min)/2 – m*th_min] / [(th_max+th_min)/2 – th_max]                                                                                                 (17)

For function v2, we set m = 1.2*v_a, so we have,

p = -1.2*v_a*th_min                                                                            (18)

n = [1.2*v_a*(th_max+th_min)/2 – 1.2*v_a*th_min] / [(th_max+th_min)/2-th_max]                                                                                                 (19)

q = 1 – n*th_max                                                                                   (20)

For function v3, we set m = 0.8*v_a, so we have,

p = -0.8*v_a*th_min                                                                             (21)

n = [0.8*v_a*(th_max+th_min)/2 – 0.8*v_a*th_min] / [(th_max+th_min)/2-th_max]                                                                                                  (22)

q = 1 – n*th_max                                                                                    (23)

1.2 Changes the Source Code

In order to add the four different evaluation functions for Pb and make it configurable, we’ll need to add a new input parameter in red.h. We add a variable func to the data structure edp.

struct edp {

    /*

     * User supplied.

     */

    int mean_pktsize;    /* avg pkt size, linked into Tcl */

    int idle_pktsize;    /* avg pkt size used during idle times */

    int bytes;        /* true if queue in bytes, false if packets */

    int wait;        /* true for waiting between dropped packets */

    int setbit;        /* true to set congestion indication bit */

    int gentle;        /* true to increases dropping prob. slowly *

                 * when ave queue exceeds maxthresh. */

    double th_min;        /* minimum threshold of average queue size */

    double th_min_pkts;    /* always maintained in packets */

    double th_max;        /* maximum threshold of average queue size */

    double th_max_pkts;     /* always maintained in packets */

    double max_p_inv;       /* 1/max_p, for max_p = maximum prob.  */

                            /* adaptive RED: the initial max_p_inv     */    

    double mark_p;        /* when p < mark_p, mark chosen packets */

                /* when p > mark_p, drop chosen packets */

        int use_mark_p;        /* use mark_p only for deciding when to drop, */

                /*   if queue is not full */

                /* Set use_mark_p true and set mark_p to 2.0 */

                /*   to always mark instead of drop */

                /*   when queue is not full */

    double q_w;        /* queue weight given to cur q size sample */

    int adaptive;        /* 0 for default RED */

                /* 1 for adaptive RED, adapting max_p */

    int cautious;           /* 0 for default RED */

                                /* 1 for not dropping/marking when the */

                                /*  instantaneous queue is much below the */

                                /*  average */

    double alpha;           /* adaptive RED: additive param for max_p */

    double beta;            /* adaptive RED: multip param for max_p */

    double interval;    /* adaptive RED: interval for adaptations */

    double targetdelay;     /* adaptive RED: target queue size */

    double top;        /* adaptive RED: upper bound for max_p */

    double bottom;        /* adaptive RED: lower bound for max_p */

                /* 0 for automatic setting */

    int feng_adaptive;    /* adaptive RED: Use the Feng et al. version */

            

    /*

     * Computed as a function of user supplied paramters.

     */

    double ptc;        /* packet time constant in packets/second */

    double delay;        /* link delay */

    int func;        /* function used to calculate Pb*/

};

In red.cc, we first bind the variable in the REDQueue constructor REDQueue::REDQueue,

bind(“function_”, &edp_.func);            //roman10: function number: 0~4

Then we change the calculate_p_new function as below,

/*

 * Calculate the drop probability.

 */

double

REDQueue::calculate_p_new(double v_ave, double th_max, int gentle, double v_a, 

    double v_b, double v_c, double v_d, double max_p)

{

    double p;

    double lm, ln, lp, lq, Xmin;

    if (gentle && v_ave >= th_max) {

        // p ranges from max_p to 1 as the average queue

        // size ranges from th_max to twice th_max 

        p = v_c * v_ave + v_d;

        } else if (!gentle && v_ave >= th_max) { 

                // OLD: p continues to range linearly above max_p as

                // the average queue size ranges above th_max.

                // NEW: p is set to 1.0 

                p = 1.0;

        } else {

                // p ranges from 0 to max_p as the average queue

                // size ranges from th_min to th_max 

        if (edp_.func == 1) {

            lm = 1.0/(log(th_max) - log(-v_b/v_a));

            ln = -lm*log(-v_b/v_a);

            p = lm*log(v_ave) + ln;

        } else if (edp_.func == 2) {

            Xmin = -v_b/v_a;

            if (v_ave < (th_max + Xmin)/2) {

                lm = 1.2*v_a;

                lp = -lm*Xmin;

                p = lm * v_ave + lp;

            } else {

            ln = (1.2*v_a*(th_max+Xmin)/2-1.2*v_a*Xmin)/((th_max+Xmin)/2-th_max);

                lq = 1.0 - ln*th_max;

                p = ln * v_ave + lq;

            }

        } else if (edp_.func == 3) {

            if (v_ave < (th_max - v_b/v_a)/2) {

            lm = 0.8*v_a;

            lp = v_b*lm/v_a;

            p = lm*v_ave + lp;            

            } else {

            ln = (0.8*v_a*(th_max+Xmin)/2-0.8*v_a*Xmin)/((th_max+Xmin)/2-th_max);

            lq = 1.0 - ln*th_max;

                p = ln * v_ave + lq;

            }

        } else if (edp_.func == 4) {

            lm = 1.0/(exp(th_max) - exp(-v_b/v_a));

            ln = -lm*exp(-v_b/v_a);

            p = lm*exp(v_ave) + ln;

            //printf("%f, %f, %f, %fn", exp(th_max), exp(-v_b/v_a), lm, v_ave);

        } else {

                p = v_a * v_ave + v_b;

        }

                // p = (v_ave - th_min) / (th_max - th_min)

                p *= max_p; 

        }

    if (p > 1.0)

        p = 1.0;

    return p;

}

2. Change ns-default.tcl

We update ns-2.35/tcl/lib/ns-default.tcl file by adding the following to red queue configuration section (search for Qeueu/RED, and add it at some lines nearby),

Queue/RED set function_ 0

This line sets the function_ to be 0 if user doesn’t supply the function_ value.

3. Test the Changes

One can run the simulation configured below to see if our changes work or not.

set ns [new Simulator]

 

#    s1                             

#       -                       

#          -                   

#    s2 ----- r1            

#                 -       

#    -                r3  - - - - - D1    

#    -            -

#             -

#    S50   -

 

set NumSenders 50

set NumReceivers 1

#read scenario, seed and bottleneck bandwidth from the command line input arguments

set Scenario [lindex $argv 0]

set function [lindex $argv 1]

set seed [lindex $argv 2]

 

puts "scenario: $Scenario; function: $function; seed: $seed"

ns-random $seed

set BufSize 100

set PktSize 1024 

#set winSize 200

#in seconds

set Duration 50 

#create all nodes: note that the order of creating the nodes matter

for {set i 1} {$i <= $NumSenders} {incr i} {

    set s($i) [$ns node]

}

set r1 [$ns node]

set d1 [$ns node]

 

 

#open the nam trace file

set nf [open out.nam w]

$ns namtrace-all $nf

 

#open the traffic trace file to record all events

set nd [open out.tr w]

$ns trace-all $nd

 

#define a finish procedure

proc finish {} {

    global ns nf nd qtf

    $ns flush-trace

    close $nf

    close $nd

    close $qtf

    #start nam

    #exec nam out.nam &

    exit 0

}

 

#link the nodes

if { $Scenario == 1 } {

    Queue/RED set thresh_ 15

    Queue/RED set maxthresh_ 45

} elseif { $Scenario == 2 } {

    Queue/RED set thresh_ 20

    Queue/RED set maxthresh_ 60

} elseif { $Scenario == 3 } {

    Queue/RED set thresh_ 25

    Queue/RED set maxthresh_ 75

} elseif { $Scenario == 4 } {

    Queue/RED set thresh_ 30

    Queue/RED set maxthresh_ 90

}

Queue/RED set queue_in_bytes_ false

Queue/RED set gentle_ false

Queue/RED set function_ $function

 

for {set i 1} {$i <= $NumSenders} {incr i} {

    $ns duplex-link $s($i) $r1 10Mb 100ms DropTail

    $ns queue-limit $s($i) $r1 $BufSize

}

#r1 d1 and d1 r1 are different

$ns duplex-link $r1 $d1 3Mb 100ms RED

$ns queue-limit $r1 $d1 $BufSize

 

#trace the queue: note that link r1 d1 is different from d1 r1

set redq [[$ns link $r1 $d1] queue]

set qtf [open queue.txt w]

$redq trace curq_

$redq trace ave_

$redq attach $qtf

 

#set up TCP connections

for {set i 1} {$i <= $NumSenders} {incr i} {

    set tcp($i) [new Agent/TCP]

    $ns attach-agent $s($i) $tcp($i)

    set sink($i) [new Agent/TCPSink]

    $ns attach-agent $d1 $sink($i)

    $ns connect $tcp($i) $sink($i)

    $tcp($i) set fid_ $i

    $tcp($i) set packetSize_ $PktSize

    #$tcp($i) set window_ $winSize

    #set up FTP over TCP connection as traffic source

    set ftp($i) [new Application/FTP]

    $ftp($i) attach-agent $tcp($i)

    $ftp($i) set type_ FTP

}

 

#schedule events for the FTP agents

set StartTime [expr [ns-random]  / 2147483647.0 / 100]

puts "starttime $StartTime"

#temporarily set to 2

for {set i 1} {$i <= $NumSenders} {incr i}  {

    $ns at $StartTime "$ftp($i) start"

    $ns at $Duration+$StartTime "$ftp($i) stop"

}

#ensure the ftp application have enough time to finish, so we +1

$ns at $Duration+$StartTime+1 "finish"

 

#run the simulation

$ns run

 

Supposed we save the file as b.tcl, a sample command to run it,

ns b.tcl 4 1 100

4. Results

I run a simulation using the 5 different evaluation functions, below are the plots of average queue size and instance queue versus time. The red lines are the average queue size and green lines are instance queue size.

imageimage

imageimage

image

Figure 2. Average Queue Size and Instance Queue Size versus Time

From the plot, we can see that v1 and v2 keeps the average queue size at a lower level than regular RED, while v3 and v4 keeps the average queue size at a higher level than regular RED. This is expected as v1 and v2 are always above the original linear function given the same average queue size value in the range of [th_min, th_max], in other words, v1 and v2 are more aggressive in terms of dropping packets when the average queue size is between th_min and th_max. On the contrast, v3 and v4 are less aggressive than regular RED.

5. Download

You can download the files mentioned in this post here.

Follow the instructions below to apply the changes (you’ll need gnuplot to plot the figures),

1. Apply the changes
1.1 copy red.cc and red.h to ns-allinone-2.34/ns-2.34/queue/
1.2 copy ns-default.tcl to ns-allinone-2.34/ns-2.34/tcl/lib/
1.3 at command line, go to ns-allinone-2.34/ns-2.34/, “sudo make”
2. Run the simulation and plot figures: ./b.py

References:

1. How to Install NS2.34 in Ubuntu: http://www.scribd.com/doc/46784839/Install-NS2-34-in-Ubuntu10-10

2. Problem description in detail http://www.comp.nus.edu.sg/~tbma/teaching/cs5229/NS2_Assignment.pdf

How to Add a New AQM Protocol in NS2

NS2 is a popular network simulator used in both industry and research. Sometimes we designed a new protocol and want to see how it performs. This article gives a brief intro of how to do this. Specifically, I illustrate the steps by adding a new Active Queuing Mechanism (AQM) protocol to ns2.

0. Download ns2, Compile it and Install it.

This is a preparation step. It’s not the focus of this post, please refer to reference 1 for details. Note that since we’re going to modify NS2 by adding our own protocol to it, we’ll need to download and source code and build it ourselves.

1. Add C++ Source Files and Update Makefile

For AQM protocols, their source files are placed under the folder ns-allinone-2.35/ns-2.35/queue/. Suppose our new protocol is named MOD, and it’s implemented in mod.cc and mod.h source files. Simply copy mod.cc and mod.h files to ns-2.35/queue/ folder.

Next we’ll need to modify the makefile so that mod.cc and mod.h can be compiled. Open ns-allinone-2.35/ns-2.35/Makefile. Look for queue/red.o and add queue/mod.o. So the line will become,

adc/simple-intserv-sched.o queue/red.o queue/mod.o

Save the changes, and type “make” at ns-allinline-2.35/ns-2.35/ directory. The newly added protocol will be built.

2. Add MOD for TCL Scripting

NS2 uses TCL for simulation configuration. So far we only builds the protocol in C++, there’re still some work needs to be done in order for the newly added protocol to be used in TCL.

2.1 Changes Files under ns-2.35/tcl/lib/

There’re a few files needs to change in order for MOD for work. I don’t want this post to be lengthy, so it’s not shown in detail, you can download the file at the end of the post, and search for MOD to see the places that have been changed.

The list of files need to change including ns-queue.tcl, ns-default.tcl, ns-route.tcl, ns-compat.tcl, and ns-lib.tcl.

2.2 Compile Again

Go to directory ns-2.35 in command line, and type “sudo make” to build ns2.

3. Download

You can download the files mentioned in the post here. A test file c.tcl is also included for your reference.

References:

1. How to Install NS2.34 in Ubuntu: http://www.scribd.com/doc/46784839/Install-NS2-34-in-Ubuntu10-10

2.  Refined Design of Random Early Detection Gateways: http://www.google.com.sg/search?sourceid=chrome&ie=UTF-8&q=Refined+Design+of+Random+Early+Detection+Gateways.