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, %f\n", 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
