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,

*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.

*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