Subject: OLSR source code

From: [email-masked]
Date: Wed, 12 Dec 2001 09:28:29 -0800

Thomas,

I see that the same OLSR implementation code that I used for
ns-2 simulations (which you say has some problems)
is still at the OLSR web site.  Perhaps you should include
a note that the code does not work properly, or offer the
fixed code.

Actually, the OLSR code worked great in ns-2 simulations for
50 nodes and for low packet rates, so I am still not sure
that I did not implement it correctly. In any case, I will rerun
the simulations with your ns-2 code.  

Regarding your ns-2 patch, which I assume gives the code you used
for your comparisons to AODV.  At the IETF meeting in London, I recall
you said that you did not use link-layer detection because the AODV 
code you used did not offer it.  However, I noticed the following 
in your patch:
 
 -#define AODV_LINK_LAYER_DETECTION
 +//#define AODV_LINK_LAYER_DETECTION
  
Perhaps you can explain this discrepancy?

Richard

---

From: Dan HE <[email-masked]>
Date: Thu, 13 Dec 2001 16:19:43 +0100

Richard,

OLSR code seems to be integrated into ns2.1b8a in my case.
but I don't have example scripts of olsr. doesn't anyone send
me the meaningfule code for comparision purpose?

Dan

---

From: [email-masked]
Date: Fri, 14 Dec 2001 10:40:41 +0100 (MET)

Richard,

> a note that the code does not work properly, or offer the

For all I know, the code presented at the WWW-site does work properly for its 
intended purpose: running on Linux in compliance with an earlier version of the 
draft. The code was never developed to run in ns2.

<SNIP>
 
> for your comparisons to AODV.

I will give no guarantees that it is exactly the same. Code evolves over time ;)

> At the IETF meeting in London, I recall
> code you used did not offer it. 

No, your memory must be playing tricks on you. I did definitely not say that. 
The ns2-code for AODV does support link-layer detections - I believe that both 
I and Charlie Perkins mentioned that during the meeting in London. I did not do 
any "comparisons" between the protocols either, btw......

I would like to remind you of the disclaimer I gave in London: that I was not 
trying to provide a comparison between two protocols (AODV and OLSR) to 
establish which is "better". I was rather pointing out that two instances of 
two protocols (in this case an instance of AODV and an instance of OLSR, 
neither of these utilizing link-layer detection) could perform almost 
identically using CBR-traffic, while TCP-performance would differ significantly.

The only point I was making then was, that performance (also) depends on the 
interaction between the transport layer and the routing protocol.

> However, I noticed the following 
> in your patch:
>  

As I am sure you will agree from the above, there is no discrepancy here.

--thomas

---

From: [email-masked]
Date: Fri, 14 Dec 2001 09:05:58 -0800

> draft. The code was never developed to run in ns2.

It's good to hear that the code works properly. That explains why OLSR
performed well in ns-2 for a 50 node network with low packet rates.
However, I do understand that you probably did not optimize the code
for performance comparison.  (Nonetheless, I have no reason to believe
that our adaptation of the OLSR implementation code to ns-2 is incorrect.)

> No, your memory must be playing tricks on you. I did definitely not say that. 

I already corrected myself in another message, as you may have noticed.
You probably said "the code" you used did not have link-layer
detection, and I misunderstood you to mean the AODV code.

Richard

---

From: Joe Macker <[email-masked]>
Date: Mon, 17 Dec 2001 11:46:54 -0500

>that our adaptation of the OLSR implementation code to ns-2 is incorrect.)

I believe that if you did not carefully rework the event handler code when porting the older Linux-based OLSR release that there would be serious issues with performance, especially regarding control packet jitter,etc.  These effects were announced as significant performance factors at the London meeting.

---

From: [email-masked]
Date: Tue, 18 Dec 2001 11:40:05 -0800

Joe,

> I believe that if you did not carefully rework the event handler code when porting 
> the older Linux-based OLSR release that there would be serious issues with performance, 
> especially regarding control packet jitter,etc.  These effects were announced as 
> significant performance factors at the London meeting.

For the record, we implemented jitter exactly as described in the latest OLSR 
draft (the relevant excerpt is included at the end of this message), except that 
we used MAXJITTER equal to 0.1 s instead of 0.5 s.  (I am not sure how using a 
jitter of 0.1 s would affect performance, but we did this so that OLSR and TBRPF 
would have the same jitter.)  We double checked the code and trace file to make
sure that this was implemented correctly.

If OLSR has serious performance problems without using jitter, then I am wondering 
why jitter is not required (MUST) instead of optional (SHOULD). (One thing that comes 
to mind is that this might violate OLSR's requirement for backward compatibility.)

Richard

Here is the relevant excerpt from the current OLSR draft:

   "As a basic implementation requirement, synchronization of control
   messages SHOULD be avoided. As a consequence, periodic OLSR messages
   should be emitted such that they avoid synchronization.

   Emission of control traffic from neighboring nodes may, for various
   reasons (mainly timer interactions with packet processing), become
   synchronized such that several neighbor nodes attempt to transmit
   control traffic simultaneously. Depending on the nature of the under-
   lying link-layer, this may or may not lead to collisions and hence
   message loss - possibly loss of several subsequent messages of the
   same type.
   
   To counter such synchronizations, the following simple strategy for
   emitting control messages is proposed. A node may add an amount of
   jitter to the interval at which messages are generated. The jitter
   must be a random value for each message generated. Thus, for a node
   utilizing jitter:

        Actual message interval = MESSAGE_INTERVAL + jitter

   Where jitter is a value, randomly selected from the interval
   [-MAXJITTER,0] and MESSAGE_INTERVAL is the value of the message
   interval specified for the message being emitted (e.g. HELLO_INTERVAL
   for HELLO messages, TC_INTERVAL for TC-messages etc.)."

---

From: Joe Macker <[email-masked]>
Date: Tue, 18 Dec 2001 16:10:08 -0500

>draft (the relevant excerpt is included at the end of this message), except that 

My issue was did you write a new event handler or modify the existing one when porting the code to ns2 (I know that source code well and it had some implementation issues not related to the spec)?

Would you be willing to post a copy of your tcl scripts? If I get time ;-) 
I, for one, might run a few trials independently and see what happens.
I don't want to go through a legal request process for test scripts, so if they can't be made more easily available, I'll produce my own.

Tranquillo, no soy un sabelotodo.

joe

---

From: [email-masked]
Date: Tue, 18 Dec 2001 19:30:42 -0800

> My issue was did you write a new event handler or modify the existing one when porting the code to n
s2 (I know that source code well and it had some implementation issues not related to the spec)?
> Tranquillo, no soy un sabelotodo.

To Joe and all, 

We used the ns-2 scheduler to call the OLSR timer() function periodically 
with jitter.  The trace file was checked to confirm that HELLO/TC messages 
were being sent with the proper jitter.

In our experiments, for both OLSR and TBRPF:
   - Link-layer detection of failures was used 
   - Data packets with no route are buffered for up to 5 seconds.
   - ARP was not used, since MAC addresses can be obtained from received 
     control packets.

The ns-2 code that is available at the OLSR web site does not do any of 
the above.  So if you want to make a fair comparison with TBRPF, you will
have to either modify the OLSR ns-2 code to forward packets in the same
way TBRPF does, or modify the TBRPF ns-2 code (more specifically the file 
phop_ns2.cc) to forward packets in the same way OLSR does.  (You can disable
link-layer detection in TBRPF by commenting out "#define LINK_LAYER_DETECTION".)

The scenario (mobility) files were generated using the cmu/setdest program, e.g.

setdest -n 100 -p 0 -s 20 -t 500 -x 1500 -y 300

and cbr files were generated by a modification of the cbrgen.tcl program
that allows the destination of each connection to change periodically
(e.g., every 30 seconds). This program is given at the end of this message.

It is very easy to request TBRPF source code at the following site

    http://www.erg.sri.com/projects/tbrpf/sourcecode.html

and we encourage everyone to do so and find out for themselves how TBRPF
compares to other protocols.  The license essentially says you can use 
the code for research purposes.

Richard

---------------
Here is the tcl file cbrgen_dynamic.tcl that generates the cbr files we used:

# ======================================================================
# Default Script Options
# ======================================================================
set opt(nn)		0		;# Number of Nodes
set opt(seed)		0.0
set opt(mc)		0
set opt(pktsize)	0

set opt(rate)		0
set opt(interval)	0.0		;# inverse of rate
set opt(type)		"cbr"
set opt(duration)	0.0
set opt(period)        30.0        ;# period at which destination changes

# ======================================================================

proc usage {} {
    global argv0

    puts "\nusage: $argv0 \[-type cbr|tcp\] \[-nn nodes\] \[-seed
    seed\] \[-mc connections\] \[-rate rate\] \[-pktsize pktsize\]
    \[-duration duration\]\n"
}

proc getopt {argc argv} {
	global opt
	lappend optlist nn seed mc rate pktsize type

	for {set i 0} {$i < $argc} {incr i} {
		set arg [lindex $argv $i]
		if {[string range $arg 0 0] != "-"} continue

		set name [string range $arg 1 end]
		set opt($name) [lindex $argv [expr $i+1]]
	}
}

proc create-cbr-connection { src dst } {
	global rng cbr_cnt opt

	set stime [$rng uniform 10.0 [expr 10.0 + $opt(period)]]

	puts "#\n# $src connecting to $dst at time $stime\n#"

	puts "set cbr_($cbr_cnt) \[\$ns_ create-connection \
		CBR \$node_($src) CBR \$node_($dst) 0\]";

	puts "\$cbr_($cbr_cnt) set packetSize_ $opt(pktsize)"
	puts "\$cbr_($cbr_cnt) set interval_ $opt(interval)"
        puts "\$cbr_($cbr_cnt) set random_ 0"
	puts "\$cbr_($cbr_cnt) set maxpkts_ 100000000"
	
	puts "\$ns_ at $stime \"\$cbr_($cbr_cnt) start\""

	switch-dest-periodically $src $dst $stime 

	incr cbr_cnt
}

proc create-tcp-connection { src dst } {
	global rng cbr_cnt opt

	set stime [$rng uniform 0.0 180.0]

	puts "#\n# $src connecting to $dst at time $stime\n#"

	puts "set tcp_($cbr_cnt) \[\$ns_ create-connection \
		TCP \$node_($src) TCPSink \$node_($dst) 0\]";
	puts "\$tcp_($cbr_cnt) set window_ 32"
	puts "\$tcp_($cbr_cnt) set packetSize_ $opt(pktsize)"

	puts "set ftp_($cbr_cnt) \[\$tcp_($cbr_cnt) attach-source FTP\]"

	puts "\$ns_ at $stime \"\$ftp_($cbr_cnt) start\""

	switch-dest-periodically $src $dst $stime 

	incr cbr_cnt
}

proc change-cbr-connection { src dst t } {
	global rng cbr_cnt opt

	set stime [expr ($t)]

	puts "#\n# $src connecting to $dst at time $stime\n#"

	puts "set cbr_($cbr_cnt) \[\$ns_ create-connection \
		CBR \$node_($src) CBR \$node_($dst) 0\]";

	puts "\$cbr_($cbr_cnt) set packetSize_ $opt(pktsize)"
	puts "\$cbr_($cbr_cnt) set interval_ $opt(interval)"
        puts "\$cbr_($cbr_cnt) set random_ 0"
	puts "\$cbr_($cbr_cnt) set maxpkts_ 100000000"
	
	puts "\$ns_ at $stime \"\$cbr_($cbr_cnt) start\""

}

proc change-tcp-connection { src dst t } {
	global rng cbr_cnt opt

	set stime [expr ($t)]

	puts "#\n# $src connecting to $dst at time $stime\n#"

	puts "set tcp_($cbr_cnt) \[\$ns_ create-connection \
		TCP \$node_($src) TCPSink \$node_($dst) 0\]";
	puts "\$tcp_($cbr_cnt) set window_ 32"
	puts "\$tcp_($cbr_cnt) set packetSize_ $opt(pktsize)"

	puts "set ftp_($cbr_cnt) \[\$tcp_($cbr_cnt) attach-source FTP\]"

	puts "\$ns_ at $stime \"\$ftp_($cbr_cnt) start\""
}

proc switch-dest-periodically { src dst t }  {
     global rng cbr_cnt opt

     set tt $t
     set v [new RandomVariable/Uniform]
     $v set min_ 0
     $v set max_ 1

     while { $tt < [expr ($opt(duration) - $opt(period))] }  {

     set tt [expr ($tt + $opt(period))]

     if { $opt(type) == "cbr" } {
          puts "\$ns_ at $tt \"\$cbr_($cbr_cnt) stop\""
     } else {
          puts "\$ns_ at $tt \"\$ftp_($cbr_cnt) stop\""
     }

while { 0 < 1 } {

        set x [$v value] 

        set dst [expr int([expr rand() * $opt(nn) + 1])] 

	if { $dst == $src } {continue;}
	if { $dst > $opt(nn) } {continue;}

	if { $opt(type) == "cbr" } {
		change-cbr-connection $src $dst $tt
	} else {
		change-tcp-connection $src $dst $tt
	}
	break;

        }

	}
}

# ======================================================================

getopt $argc $argv

if { $opt(type) == "" } {
    usage
    exit
} elseif { $opt(type) == "cbr" } {
    if { $opt(nn) == 0 || $opt(seed) == 0.0 || $opt(mc) == 0 || $opt(rate) == 0 } {
	usage
	exit
    }

    set opt(interval) [expr 1.0 / $opt(rate)]
    if { $opt(interval) <= 0.0 } {
	puts "\ninvalid sending rate $opt(rate), interval $opt(interval)\n"
	exit
    }
}

puts "#\n# nodes: $opt(nn), max conn: $opt(mc), send rate: $opt(interval), seed: $opt(seed)\n#"

set rng [new RNG]
$rng seed $opt(seed)

set u [new RandomVariable/Uniform]
$u set min_ 0
$u set max_ 100
$u use-rng $rng

set cbr_cnt 0
set src_cnt 0

for {set i 1} {$i <= $opt(nn) } {incr i} {

	set x [$u value]

	if {$x < 0} {continue;}

	incr src_cnt

	set dst [expr ($i+1) % [expr $opt(nn) + 1] ]
	if { $dst == 0 } {
		set dst [expr $dst + 1]
	}

	if { $opt(type) == "cbr" } {
		create-cbr-connection $i $dst
	} else {
		create-tcp-connection $i $dst
	}

	if { $cbr_cnt == $opt(mc) } {
		break
	}
}

puts "#\n#Total sources/connections: $src_cnt/$cbr_cnt\n#"